제출 #231153

#제출 시각아이디문제언어결과실행 시간메모리
231153duality청소 (JOI20_sweeping)C++11
75 / 100
18047 ms1449336 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 ---------- template<typename T1,typename T2> ostream& operator<<(ostream& output,const pair<T1,T2> &p) { output << "(" << p.first << "," << p.second << ")"; return output; } template<typename T> ostream& operator<<(ostream& output,const vector<T> &v) { unsigned int i; bool f = 1; for (i = 0; i < v.size(); i++) { if (!f) output << " "; output << v[i]; f = 0; } return output; } template<typename T> ostream& operator<<(ostream& output,const list<T> &l) { typename list<T>::const_iterator it; bool f = 1; for (it = l.begin(); it != l.end(); it++) { if (!f) output << " "; output << *it; f = 0; } return output; } template<typename T1,typename T2> ostream& operator<<(ostream& output,const map<T1,T2> &m) { typename map<T1,T2>::const_iterator it; bool f = 1; for (it = m.begin(); it != m.end(); it++) { if (!f) output << " "; output << "(" << it->first << " -> " << it->second << ")"; f = 0; } return output; } template<typename T> ostream& operator<<(ostream& output,const set<T> &s) { typename set<T>::const_iterator it; bool f = 1; for (it = s.begin(); it != s.end(); it++) { if (!f) output << " "; output << *it; f = 0; } return output; } int X[1500000],Y[1500000]; map<int,pii> MM; struct func { int l,r,d,u,x,y; }; vector<func> f; int insert(map<pii,pii> &M,int l,int r,pii p) { //debug "here",l,r,p; //debug M; auto it = M.upper_bound(mp(l,2e9)); if (it != M.begin()) { it--; pair<pii,pii> q = *it; if ((q.first.first <= l) && (l <= q.first.second)) { M.erase(it); if (l-1 >= q.first.first) M[mp(q.first.first,l-1)] = q.second; M[mp(l,q.first.second)] = q.second; } } //debug M; it = M.upper_bound(mp(r,2e9)); if (it != M.begin()) { it--; pair<pii,pii> q = *it; if ((q.first.first <= r) && (r <= q.first.second)) { M.erase(it); if (r+1 <= q.first.second) M[mp(r+1,q.first.second)] = q.second; M[mp(q.first.first,r)] = q.second; } } //debug M; it = M.lower_bound(mp(l,0)); while ((it != M.end()) && (it->first.second <= r)) assert(it->first.second >= l),it = M.erase(it); M[mp(l,r)] = p; //debug M; return 0; } struct node { node *l,*r; map<pii,pii> M; int update(int s,int e,int as,int ae,int d,int u,pii p) { //cout<<as<<","<<ae<<","<<d<<","<<u<<": "<<p.first<<","<<p.second<<endl; //cout<<s<<","<<e<<endl; if ((s >= as) && (e <= ae)) { insert(M,d,u,p); return 0; } int mid = (s+e) / 2; if (as <= mid) { if (l == NULL) l = new node(),l->l = l->r = NULL; l->update(s,mid,as,ae,d,u,p); } if (ae >= mid+1) { if (r == NULL) r = new node(),r->l = r->r = NULL; r->update(mid+1,e,as,ae,d,u,p); } return 0; } pii query(int s,int e,int q,int qy) { int mid = (s+e) / 2; pii ans = mp(-1,-1); auto it = M.upper_bound(mp(qy,2e9)); if (it != M.begin()) { it--; if ((it->first.first <= qy) && (qy <= it->first.second)) ans = it->second; } if (q <= mid) { if (l != NULL) { pii ans2 = l->query(s,mid,q,qy); if (ans.first+ans.second < ans2.first+ans2.second) ans = ans2; } } else { if (r != NULL) { pii ans2 = r->query(mid+1,e,q,qy); if (ans.first+ans.second < ans2.first+ans2.second) ans = ans2; } } return ans; } }; node *root; int update(int x,int t,int N) { auto it = MM.lower_bound(x); if (it->first == x) return 0; auto it2 = it; it2--; if (t == 1) { f.pb((func){it2->first-it2->second.first,x-1,N-it->first,N-x-1,x,-1}); f.pb((func){it2->first-it2->second.first,x-1,N-it->first-it->second.second,N-it->first,x,N-it->first}); MM[x] = mp(it2->second.first+x-it2->first,0); } else { f.pb((func){it2->first,x-1,N-it->first-it->second.second,N-x-1,-1,N-x}); f.pb((func){it2->first-it2->second.first,it2->first,N-it->first-it->second.second,N-x-1,it2->first,N-x}); MM[x] = mp(0,it->second.second+it->first-x); } func a = f[f.size()-2],b = f.back(); swap(a,b); assert((a.l >= 0) && (a.d >= 0) && (a.r <= N+5) && (a.u <= N+5)); if ((a.l <= a.r) && (a.d <= a.u)) root->update(0,N+5,a.l,a.r,a.d,a.u,mp(a.x,a.y)); swap(a,b);assert((a.l >= 0) && (a.d >= 0) && (a.r <= N+5) && (a.u <= N+5)); if ((a.l <= a.r) && (a.d <= a.u)) root->update(0,N+5,a.l,a.r,a.d,a.u,mp(a.x,a.y)); return 0; } vpii ops; int t[1000000],p[1000000],l[1000000],a[1000000],b[1000000]; int tree[1 << 22],lazy[1 << 22]; int prop(int s,int e,int i) { tree[i] = max(tree[i],lazy[i]); if (s != e) { lazy[2*i+1] = max(lazy[2*i+1],lazy[i]); lazy[2*i+2] = max(lazy[2*i+2],lazy[i]); } lazy[i] = 0; return 0; } int update(int s,int e,int as,int ae,int i,int num,int t) { prop(s,e,i); if ((s > ae) || (e < as)) return 0; else if ((s >= as) && (e <= ae)) { lazy[i] = num; if (t) tree[i] = num; prop(s,e,i); return 0; } int mid = (s+e) / 2; update(s,mid,as,ae,2*i+1,num,t),update(mid+1,e,as,ae,2*i+2,num,t); tree[i] = max(tree[2*i+1],tree[2*i+2]); return 0; } int query(int s,int e,int qs,int qe,int i) { prop(s,e,i); if ((s > qe) || (e < qs)) return 0; else if ((s >= qs) && (e <= qe)) return tree[i]; int mid = (s+e) / 2; return max(query(s,mid,qs,qe,2*i+1),query(mid+1,e,qs,qe,2*i+2)); } int main() { int i; int N,M,Q; int T,P,L,A,B,sub2 = 1; scanf("%d %d %d",&N,&M,&Q); for (i = 0; i < M; i++) scanf("%d %d",&X[i],&Y[i]); for (i = 0; i < Q; i++) { scanf("%d",&t[i]); if (t[i] == 1) scanf("%d",&p[i]); else if (t[i] <= 3) scanf("%d",&l[i]); else scanf("%d %d",&a[i],&b[i]); if (t[i] == 3) sub2 = 0; } if (sub2) { vpii possy; int c = M; for (i = 0; i < M; i++) possy.pb(mp(Y[i],i)); for (i = 0; i < Q; i++) { if (t[i] == 4) possy.pb(mp(b[i],c++)); } sort(possy.begin(),possy.end()); for (i = 0; i < M; i++) { int x = lower_bound(possy.begin(),possy.end(),mp(Y[i],i))-possy.begin(); update(0,c-1,x,x,0,X[i],1); } int c2 = M; for (i = 0; i < Q; i++) { if (t[i] == 1) { int x = lower_bound(possy.begin(),possy.end(),mp(Y[p[i]-1],p[i]-1))-possy.begin(); printf("%d %d\n",query(0,c-1,x,x,0),Y[p[i]-1]); } else if (t[i] == 2) { int x = upper_bound(possy.begin(),possy.end(),mp(l[i],(int) 2e9))-possy.begin()-1; update(0,c-1,0,x,0,N-l[i],0); } else { X[c2] = a[i],Y[c2++] = b[i]; int x = lower_bound(possy.begin(),possy.end(),mp(Y[c2-1],c2-1))-possy.begin(); update(0,c-1,x,x,0,X[c2-1],1); } } return 0; } MM[0] = MM[N+1] = mp(0,0); root = new node; root->l = root->r = NULL; for (i = 0; i < Q; i++) { T = t[i]; if (T == 1) { P = p[i],P--; pii ans = root->query(0,N+6,X[P],Y[P]); int xx = X[P],yy = Y[P]; if (ans.first != -1) xx = ans.first; if (ans.second != -1) yy = ans.second; printf("%d %d\n",xx,yy);/* pii p = mp(xx,yy); int j; for (j = f.size()-1; j >= 0; j--) { if ((X[P] >= f[j].l) && (X[P] <= f[j].r) && (Y[P] >= f[j].d) && (Y[P] <= f[j].u)) { int xx = X[P],yy = Y[P]; if (f[j].x != -1) xx = f[j].x; if (f[j].y != -1) yy = f[j].y; printf("o:%d %d\n",xx,yy); assert(p == mp(xx,yy)); break; } } if (j < 0) printf("o:%d %d\n",X[P],Y[P]),assert(p == mp(X[P],Y[P]));*/ } else if (T == 2) { L = l[i]; ops.pb(mp(T,L)); update(N-L,1,N+1); } else if (T == 3) { L = l[i]; ops.pb(mp(T,L)); update(L+1,2,N+1); } else { A = a[i],B = b[i]; break; } } if (i < Q) { int pp = i; for (i = 0; i < ops.size(); i++) { int j; for (j = 0; j < M; j++) { if (ops[i].first == 2) { if ((Y[j] <= ops[i].second) && (X[j] < N-ops[i].second)) X[j] = N-ops[i].second; } else { if ((X[j] <= ops[i].second) && (Y[j] < N-ops[i].second)) Y[j] = N-ops[i].second; } } } X[M++] = A,Y[M-1] = B; for (i = pp+1; i < Q; i++) { T = t[i]; if (T == 1) { P = p[i],P--; printf("%d %d\n",X[P],Y[P]); } else if (T == 2) { L = l[i]; int j; for (j = 0; j < M; j++) { if ((Y[j] <= L) && (X[j] < N-L)) X[j] = N-L; } } else if (T == 3) { L = l[i]; int j; for (j = 0; j < M; j++) { if ((X[j] <= L) && (Y[j] < N-L)) Y[j] = N-L; } } else { A = a[i],B = b[i]; X[M++] = A,Y[M-1] = B; } } } return 0; }

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

sweeping.cpp: In function 'int main()':
sweeping.cpp:342:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < ops.size(); i++) {
                     ~~^~~~~~~~~~~~
sweeping.cpp:256: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:257:34: 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]);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:259:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&t[i]);
         ~~~~~^~~~~~~~~~~~
sweeping.cpp:260:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         if (t[i] == 1) scanf("%d",&p[i]);
                        ~~~~~^~~~~~~~~~~~
sweeping.cpp:261:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         else if (t[i] <= 3) scanf("%d",&l[i]);
                             ~~~~~^~~~~~~~~~~~
sweeping.cpp:262:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         else scanf("%d %d",&a[i],&b[i]);
              ~~~~~^~~~~~~~~~~~~~~~~~~~~
#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...