글 읽기 - 시간 초과가 걸립니다...

wnsgur1714 4년 전 1

세그먼트 트리를 만들고 이를 내림차순으로 정렬해서 순차탐색하여 찾는 값을 넘는 경우에 남은 숫자들의 개수를 더했는데요....

제 코드가 시간초과가 걸립니다.

제가 생각하기에 세그먼트 트리를 만들고 내림차순으로 정렬하는 것 때문에 걸리는 게 아니라 일부 테스트 케이스에서 순차탐색 때문에 시간이 초과되는 것 같습니다.

탐색에 걸리는 시간을 더 줄일 수 있는 방법이 있을까요?

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, q, htv/*have to find*/;
int arr[1000011];
vector<int> tree[2000021];

void mtst(int node, int start, int endd){//make the segment tree
    for(int i = start; i <= endd ; i++){
        tree[node].push_back(arr[i]);
    }
    if(start != endd){
        mtst(node*2, start, (start+endd)/2);
        mtst(node*2+1, (start+endd)/2+1, endd);
    }
}

void stst(int node, int start, int endd){//sort the segment tree
    sort(tree[node].begin(), tree[node].end());
    if(start != endd){
        stst(node*2, start, (start+endd)/2);
        stst(node*2+1, (start+endd)/2+1, endd);
    }
}

int fist(int node, int start, int endd, int ns/*need start*/, int nd/*need end*/){//find in segment tree
    int num = 0;
    if(ns <= start && nd >= endd){
        // 여기부터
        for(int i = 0 ; i < tree[node].size() ; i++){
            if(tree[node][i] > htv){
                num += tree[node].size()-i;
                break;
            }
        }
        // 여기까지
    }
    else if(ns > endd || nd < start){

    }
    else if((ns >= start && nd >= endd) || (nd <= endd && ns <= start) || (nd >= start && nd <= endd)){
        num += fist(node*2, start, (start+endd)/2, ns, nd);
        num += fist(node*2+1, (start+endd)/2+1, endd, ns, nd);
    }
    return num;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio();
    cin >> n;
    for(int i = 1 ; i <= n ; i++){
        cin >> arr[i];
    }
    mtst(1, 1, n);
    stst(1, 1, n);
    cin >> q;
    for(int i = 0 ; i < q ; i++){
        int a, b;
        cin >> a >> b >> htv;
        cout << fist(1, 1, n, a, b) << endl;
    }
}

djm03178 4년 전 2

일단 이 문제는 세그먼트 트리의 일종인 머지소트 트리를 사용해서 효율적으로 해결할 수 있는 문제입니다.

그리고 sync_with_stdio에 아무런 인자를 주지 않으면 기본 인자가 true가 되기 때문에 안 쓰는 것과 아무런 차이가 없습니다. false를 인자로 줘야 합니다.

그리고 endl을 쓰면 cin.tie(0)도 무용지물이 됩니다. cin이 호출될 때마다 cout이 flush되는 것을 막으려고 cin.tie(0)을 쓴 건데, endl을 쓰면 cout가 강제로 flush되기 때문입니다. '\n'을 대신 사용하세요.

wnsgur1714 4년 전 1

그렇다면

순차 탐색 대신 이분 탐색을 쓰고,

sync_with_stdio(false);를 바꾸고,

endl을 "\n"로 바꾸면 시간 초과가 해결되나요?

아니면 아예 알고리즘이 잘못된 건가요?

wnsgur1714 4년 전 0

해결됬습니다!

처음에는 직접 이분 탐색을 쓰니 시간 초과가 걸렸었는데, upper_bound로 쓰니 해결되네요.

감사합니다!

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

문제

문제

출처

ICPC

시간 초과가 걸립니다...

wnsgur1714 4년 전 1

djm03178 4년 전 2

wnsgur1714 4년 전 1

wnsgur1714 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말