NERD2 시간초과 질문 좀 받아주세요

  • betain24
    betain24
    #include <algorithm>
    #include <stdio.h>
    #include <map>
    #include <cstring>
    using namespace std;
    
    map<int, int> m;
    //x, y가 다른것에 포함되었는지 확인
    bool isinclude(int x, int y){
        map<int, int>::iterator it;
        it = m.lower_bound(x);
        if(it == m.end()) return false;
        return y < it->second;
    }
    
    int main(){
        int tc;
        scanf("%d", &tc);
        while(tc--){
            m.clear();
            int n, cnt=0, sum=0;
            scanf("%d", &n);
            for(int i=0;i<n;i++){
                int x, y;
                scanf("%d %d", &x, &y);
                if(isinclude(x, y)) sum+=cnt;
                else{
                    map<int, int>::iterator it;
                    it = m.lower_bound(x);
                    //x보다 큰 값이 없으니 자기가 가장 작다.
                    //그래서 그냥 삽입
                    if(it==m.begin()){
                        m[x] = y;
                        cnt++;
                        sum+=cnt;
                    }
                    else{
                        //큰거에서 하나뺀것
                        it--;
                        //그게 처음이고 it의 y보다 크면 삭제
                        if(it==m.begin()){
                            if(y > it->second){
                                cnt--; 
                                m.erase(it);
                            }
                        }
                        else{
                            //y가 it의 y보다 클때까지
                            while( y > it->second ){
                                cnt--;
                                //탈출문
                                if(it==m.begin()){
                                    m.erase(it);
                                    break;
                                }
                                //그것을 삭제하고 it--
                                m.erase(it--);
                            }
                        }
                        //삽입
                        m[x] = y; 
                        cnt++;
                        sum+=cnt;
                    }
                }
            }
            printf("%d\n", sum);
        }
    }
    

    무한루프 도는것같지않은데 어디서 시간초과가 날까요? ㅠㅠ


    8년 전
1개의 댓글이 있습니다.
  • plzrun
    plzrun

    ㅋㅋㅋㅋㅋㅋㅋㅋㅋ


    8년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.