글 읽기 - 시간초과 질문입니다....

wnsgur1714 4년 전 0

Mo's algorithm에 map<int, list<int>>로 풀었는데 시간초과가 걸립니다...

이문제 map으로는 풀 수 없나요?

#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#include <list>

using namespace std;

struct qy{
    int start;
    int end;
    int number;
    int value;
};

int arr[100001];
map<int, list<int>> number;
qy quary[100001];
int gg;

bool stq(qy a, qy b){//sort the quary
    int ae = a.end/gg;
    int be = b.end/gg;
    if(ae > be){
        return false;
    }
    else if(ae == be){
        if(a.start >= b.start){
            return false;
        }
        else{
            return true;
        }
    }
    else{
        return true;
    }
}

bool stqbn(qy a, qy b){//sort th quary by number
    if(a.number > b.number){
        return false;
    }
    else{
        return true;
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m, k;
    cin >> n >> k;
    gg = sqrt(n);
    for(int i = 1 ; i <= n ; i++){
        cin >> arr[i];
    }
    cin >> m;
    for(int i = 0 ; i < m ; i++){
        cin >> quary[i].start >> quary[i].end;
        quary[i].number = i;
    }

    sort(quary, quary+m, stq);/* 쿼리들을 Mo's algorithm으로 정렬*/

    for(int i = quary[0].start ; i <= quary[0].end ; i++){
        number[arr[i]].push_back(i);
    }
    map<int, list<int>>::iterator it; /* 맵을 순차탐색 */
    int maxx = 0;
    for(it = number.begin() ; it != number.end() ; it++){
        int mx = (*it).second.back() - (*it).second.front();
        if(mx > maxx){
            maxx = mx;
        }
    }
    quary[0].value = maxx;
    for(int i = 1 ; i < m ; i++){
        if(quary[i].start < quary[i-1].start){
            for(int j = quary[i-1].start-1 ; j >= quary[i].start ; j--){
                number[arr[j]].push_front(j);
            }
        }
        else if(quary[i].start > quary[i-1].start){
            for(int j = quary[i-1].start ; j < quary[i].start ; j++){
                number[arr[j]].pop_front();
                if(number[arr[j]].empty()){ /*list에 남아있는 수가 없다면 map에서 제거*/
                    number.erase(arr[j]);
                }
            }
        }
        if(quary[i].end > quary[i-1].end){
            for(int j = quary[i-1].end+1 ; j <= quary[i].end ; j++){
                number[arr[j]].push_back(j);
            }
        }
        else if(quary[i].end < quary[i-1].end){
            for(int j = quary[i-1].end ; j > quary[i-1].end ; j++){
                number[arr[j]].pop_back();
                if(number[arr[j]].empty()){ /*list에 남아있는 수가 없다면 map에서 제거*/
                    number.erase(arr[j]);
                }
            }
        }
        map<int, list<int>>::iterator it; /* 맵을 순차탐색*/
        int maxx = 0;
        for(it = number.begin() ; it != number.end() ; it++){
            int mx = (*it).second.back() - (*it).second.front();
            if(mx > maxx){
                maxx = mx;
            }
        }
        quary[i].value = maxx;

    }
    sort(quary, quary+m, stqbn); /* 출력을 위해 다시 쿼리 순서대로 정렬*/
    for(int i = 0 ; i < m ; i++){
        cout << quary[i].value << "\n";
    }
}

line_jin 4년 전 0

O(N^2)되도록 구성하셨는데 이는 N이 2~4만정도까지일때 가능합니다.

O(NlogN)정도로 구성해야 가능할듯 보입니다.

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

문제

문제

출처

ICPC

시간초과 질문입니다....

wnsgur1714 4년 전 0

line_jin 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말