글 읽기 - multiset에 관하여 질문있습니다.

jcu011 4년 전 0

코드에서 multiset인 CD를 vector로 바꿔서 AC를 받았는데요

multiset을 사용했을때에는 시간초과를 맞았습니다.

어디서 시간이 많이 차이가 나는건가요 ??

단순히 퀵소트가 더 빨라서 그런건가요 ??

#include<bits/stdc++.h>
using namespace std;

vector<int> ABCD[4];
vector<int> AB;
multiset<int> CD;
long long cnt=0;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N,t; cin>>N;
    
    for(int i=0; i<N; i++) {
        for(int j=0; j<4; j++){
            cin>>t;
            ABCD[j].push_back(t);
        }
    }

    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            AB.push_back(ABCD[0][i]+ABCD[1][j]);
            CD.insert(-ABCD[2][i]-ABCD[3][j]);
        }
    }

    for(auto val : AB){
        auto it = CD.equal_range(val);
        cnt += distance(it.first, it.second);
    }

    cout<<cnt;
}

bupjae 4년 전 0

30번째 줄 distance 의 시간복잡도는 it.first 와 it.second 의 거리에 비례합니다.

이 때문에 28~31번째 줄의 반복문의 시간복잡도는 O(n^4) 가 됩니다.

jcu011 4년 전 0

@bupjae 현재 제출된 제 풀이는 다른풀이지만 distance를 써서 AC를 받았구요 distance의 시간복잡도가 그 거리에 비례한다고 해도 시간복잡도는 O(n^4)이 안나옵니다

bupjae 4년 전 1

제출 번호 19339254 에서의 distance 함수의 시간복잡도는 상수시간 입니다.

distance 함수의 시간복잡도는 iterator 의 종류에 따라서 달라집니다.

jcu011 4년 전 0

@bupjae distance의 시간복잡도가 O(n)이라고 잘못 알고 있었네요.

정말 감사합니다 !

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

multiset에 관하여 질문있습니다.

jcu011 4년 전 0

bupjae 4년 전 0

jcu011 4년 전 0

bupjae 4년 전 1

jcu011 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말