제출 #232078

#제출 시각아이디문제언어결과실행 시간메모리
232078duality청소 (JOI20_sweeping)C++11
100 / 100
12627 ms249792 KiB
#define DEBUG 0 #include <bits/stdc++.h> using namespace std; #if DEBUG // basic debugging macros int __i__,__j__; #define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl #define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl #define printVar(n) cout<<#n<<": "<<n<<endl #define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl #define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;} #define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;} // advanced debugging class // debug 1,2,'A',"test"; class _Debug { public: template<typename T> _Debug& operator,(T val) { cout << val << endl; return *this; } }; #define debug _Debug(), #else #define printLine(l) #define printLine2(l,c) #define printVar(n) #define printArr(a,l) #define print2dArr(a,r,c) #define print2dArr2(a,r,c,l) #define debug #endif // define #define MAX_VAL 999999999 #define MAX_VAL_2 999999999999999999LL #define EPS 1e-6 #define mp make_pair #define pb push_back // typedef typedef unsigned int UI; typedef long long int LLI; typedef unsigned long long int ULLI; typedef unsigned short int US; typedef pair<int,int> pii; typedef pair<LLI,LLI> plli; typedef vector<int> vi; typedef vector<LLI> vlli; typedef vector<pii> vpii; typedef vector<plli> vplli; // ---------- END OF TEMPLATE ---------- int X[1500000],Y[1500000],A[1500000]; vpii updates,queries; pii ans[1500000]; class comp1 { public: bool operator()(int a,int b) { if (ans[a].first == ans[b].first) return a < b; else return ans[a].first < ans[b].first; } }; class comp2 { public: bool operator()(int a,int b) { if (ans[a].second == ans[b].second) return a < b; else return ans[a].second < ans[b].second; } }; set<int,comp1> S1[1500000]; set<int,comp2> S2[1500000]; map<int,int> MM; int findAns(int l,int r,vi q,int N) { if (q.empty()) return 0; int i; vi c; for (i = 0; i < q.size(); i++) { int s = A[queries[q[i]].first],e = queries[q[i]].second; if ((e < l) || (s > r)) continue; if ((l >= s) && (r <= e)) S1[0].insert(q[i]),S2[0].insert(q[i]); else c.pb(q[i]); } if (!S1[0].empty()) { MM[0] = 0,MM[N] = -1; int x = 1; for (i = l; i <= r; i++) { if (MM.count(updates[i].second)) continue; int u = (--MM.lower_bound(updates[i].second))->second; MM[updates[i].second] = x++; if (updates[i].first == 1) { auto it = S2[u].begin(),it2 = S2[u].end(); int f = -1; while (1) { if ((it != S2[u].end()) && (ans[*it].second < N-updates[i].second)) it++; else { f = 0; break; } if ((it2 == S2[u].begin()) || (ans[*(--it2)].second < N-updates[i].second)) { f = 1; break; } } if (f) { swap(S1[u],S1[x-1]),swap(S2[u],S2[x-1]); it2 = S2[x-1].end(); while ((it2 != S2[x-1].begin()) && (ans[*(--it2)].second >= N-updates[i].second)) { S1[u].insert(*it2),S2[u].insert(*it2); S1[x-1].erase(*it2),it2 = S2[x-1].erase(it2); } } else { it = S2[u].begin(); while ((it != S2[u].end()) && (ans[*it].second < N-updates[i].second)) { S1[x-1].insert(*it),S2[x-1].insert(*it); S1[u].erase(*it),it = S2[u].erase(it); } } } else { auto it = S1[u].begin(),it2 = S1[u].end(); int f = -1; while (1) { if ((it != S1[u].end()) && (ans[*it].first < updates[i].second)) it++; else { f = 0; break; } if ((it2 == S1[u].begin()) || (ans[*(--it2)].first < updates[i].second)) { f = 1; break; } } if (f) { it2 = S1[u].end(); while ((it2 != S1[u].begin()) && (ans[*(--it2)].first >= updates[i].second)) { S1[x-1].insert(*it2),S2[x-1].insert(*it2); S2[u].erase(*it2),it2 = S1[u].erase(it2); } } else { swap(S1[u],S1[x-1]),swap(S2[u],S2[x-1]); it = S1[x-1].begin(); while ((it != S1[x-1].end()) && (ans[*it].first < updates[i].second)) { S1[u].insert(*it),S2[u].insert(*it); S2[x-1].erase(*it),it = S1[x-1].erase(it); } } } } for (auto it = MM.begin(); it->second != -1; it++) { auto it2 = it; it2++; int x1 = it->first,x2 = it2->first; for (auto it3 = S1[it->second].begin(); it3 != S1[it->second].end(); it3++) { ans[*it3].first = max(ans[*it3].first,x1); ans[*it3].second = max(ans[*it3].second,N-x2); } S1[it->second].clear(),S2[it->second].clear(); } MM.clear(); } if (l != r) { int m = (l+r) / 2; findAns(l,m,c,N),findAns(m+1,r,c,N); } return 0; } int main() { int i; int N,M,Q; int T,P,L; scanf("%d %d %d",&N,&M,&Q); for (i = 0; i < M; i++) scanf("%d %d",&X[i],&Y[i]),A[i] = 0; for (i = 0; i < Q; i++) { scanf("%d",&T); if (T == 1) { scanf("%d",&P),P--; queries.pb(mp(P,(int) updates.size()-1)); } else if (T == 2) { scanf("%d",&L); updates.pb(mp(1,N-L)); } else if (T == 3) { scanf("%d",&L); updates.pb(mp(2,L+1)); } else { scanf("%d %d",&X[M],&Y[M]); A[M++] = updates.size(); } } vi q; for (i = 0; i < queries.size(); i++) ans[i] = mp(X[queries[i].first],Y[queries[i].first]),q.pb(i); findAns(0,(int) updates.size()-1,q,N+1); for (i = 0; i < queries.size(); i++) printf("%d %d\n",ans[i].first,ans[i].second); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

sweeping.cpp: In function 'int findAns(int, int, vi, int)':
sweeping.cpp:82:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < q.size(); i++) {
                 ~~^~~~~~~~~~
sweeping.cpp: In function 'int main()':
sweeping.cpp:200:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < queries.size(); i++) ans[i] = mp(X[queries[i].first],Y[queries[i].first]),q.pb(i);
                 ~~^~~~~~~~~~~~~~~~
sweeping.cpp:202:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < queries.size(); i++) printf("%d %d\n",ans[i].first,ans[i].second);
                 ~~^~~~~~~~~~~~~~~~
sweeping.cpp:178:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d",&N,&M,&Q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:179:55: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < M; i++) scanf("%d %d",&X[i],&Y[i]),A[i] = 0;
                             ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
sweeping.cpp:181:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&T);
         ~~~~~^~~~~~~~~
sweeping.cpp:183:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&P),P--;
             ~~~~~~~~~~~~~~^~~~
sweeping.cpp:187:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&L);
             ~~~~~^~~~~~~~~
sweeping.cpp:191:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&L);
             ~~~~~^~~~~~~~~
sweeping.cpp:195:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d",&X[M],&Y[M]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...