NERD2 시간초과 질문 좀 받아주세요 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 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ 8년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
betain24
무한루프 도는것같지않은데 어디서 시간초과가 날까요? ㅠㅠ
8년 전