제출 #171247

#제출 시각아이디문제언어결과실행 시간메모리
171247arnold518새 집 (APIO18_new_home)C++14
47 / 100
5134 ms659792 KiB
#pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 3e5; const int INF = 2e8; struct Data { int x, t, a, b; }; struct Query { int l, y, p; }; int N, K, Q, C; Data A[MAXN*2+10]; Query query[MAXN+10]; vector<int> comp; int ans[MAXN+10]; int getcomp(int x) { return lower_bound(comp.begin(), comp.end(), x)-comp.begin()+1; } struct Line { int x, y; Line() {} Line(int x, int y) : x(x), y(y) {} bool operator < (const Line &p) const { return pii(x, y)<pii(p.x, p.y); } bool operator == (const Line &p) const { return pii(x, y)==pii(p.x, p.y); } }; Line Line1(int x, int y) { return Line(x, y-x); } Line Line2(int x, int y) { return Line(y, y-x); } multiset<int> S[MAXN+10]; vector<Line> lcomp; unordered_map<ll, int> MM; //================================================== void pushLine1(int x, int y) { Line p=Line1(x, y); lcomp.push_back(p); } void pushLine2(int x, int y) { Line p=Line2(x, y); lcomp.push_back(p); } int f(Line t) { return MM[t.x*INF*10ll+t.y]; } //================================================== vector<pii> M1; vector<Line> tree1[MAXN*12+10]; void update1(int node, int tl, int tr, int l, int r, Line val) { if(l<=tl && tr<=r) { tree1[node].push_back(val); return; } if(r<tl || tr<l) return; int mid=tl+tr>>1; update1(node*2, tl, mid, l, r, val); update1(node*2+1, mid+1, tr, l, r, val); } void pushLine1(int x, int y, int t) { Line p=Line1(x, y); int q=f(p); if(M1[q].second==0) M1[q].first=t; M1[q].second++; } void popLine1(int x, int y, int t) { Line p=Line1(x, y); int q=f(p); M1[q].second--; if(M1[q].second==0) update1(1, 1, C, M1[q].first, t, p); } //================================================== vector<pii> M2; vector<Line> tree2[MAXN*12+10]; void update2(int node, int tl, int tr, int l, int r, Line val) { if(l<=tl && tr<=r) { tree2[node].push_back(val); return; } if(r<tl || tr<l) return; int mid=tl+tr>>1; update2(node*2, tl, mid, l, r, val); update2(node*2+1, mid+1, tr, l, r, val); } void pushLine2(int x, int y, int t) { Line p=Line2(x, y); int q=f(p); if(M2[q].second==0) M2[q].first=t; M2[q].second++; } void popLine2(int x, int y, int t) { Line p=Line2(x, y); int q=f(p); M2[q].second--; if(M2[q].second==0) update2(1, 1, C, M2[q].first, t, p); } //================================================== vector<Query> tree3[MAXN*12+10]; vector<int> tree4[MAXN*12+10]; void update3(int node, int tl, int tr, int pos, Query val) { tree3[node].push_back(val); if(tl==tr) return; int mid=tl+tr>>1; if(pos<=mid) update3(node*2, tl, mid, pos, val); else update3(node*2+1, mid+1, tr, pos, val); } void update4(int node, int tl, int tr, int l, int r, int val) { if(l<=tl && tr<=r) { tree4[node].push_back(val); return; } if(r<tl || tr<l) return; int mid=tl+tr>>1; update4(node*2, tl, mid, l, r, val); update4(node*2+1, mid+1, tr, l, r, val); } int SS[MAXN+10], cnt=0; void dfs(int node, int tl, int tr) { int i, j; //printf("%d %d %d\n", node, tl, tr); //printf("==============S\n"); //for(auto it : tree1[node]) printf("%d %d / ", it.x, it.y); printf("\n"); //for(auto it : tree2[node]) printf("%d %d / ", it.x, it.y); printf("\n"); //for(auto it : tree3[node]) printf("%d %d / ", it.l, it.y); printf("\n"); //printf("==============E\n"); sort(tree1[node].begin(), tree1[node].end(), [&](const Line &p, const Line &q) { return p.x!=q.x ? p.x<q.x : p.y<q.y; }); sort(tree3[node].begin(), tree3[node].end(), [&](const Query &p, const Query &q) { return p.l<q.l; }); for(auto it : tree4[node]) { if(SS[it]==0) cnt++; SS[it]++; } int val=-1; for(i=0, j=0; i<tree3[node].size(); i++) { Query now=tree3[node][i]; for(; j<tree1[node].size() && tree1[node][j].x<=now.l; j++) { Line t=tree1[node][j]; val=max(val, t.x+t.y); ans[now.p]=max(ans[now.p], val-now.l); //printf("!%d %d\n", i, j); } if(j) j--; } sort(tree2[node].begin(), tree2[node].end(), [&](const Line &p, const Line &q) { return p.x!=q.x ? p.x>q.x : p.y<q.y; }); sort(tree3[node].begin(), tree3[node].end(), [&](const Query &p, const Query &q) { return p.l>q.l; }); val=INF+1; for(i=0, j=0; i<tree3[node].size(); i++) { Query now=tree3[node][i]; for(; j<tree2[node].size() && tree2[node][j].x>=now.l; j++) { Line t=tree2[node][j]; val=min(val, t.x-t.y); ans[now.p]=max(ans[now.p], now.l-val); } if(j) j--; } if(tl==tr) { if(cnt!=K) for(auto it : tree3[node]) ans[it.p]=-2; for(auto it : tree4[node]) { SS[it]--; if(SS[it]==0) cnt--; } return; } int mid=tl+tr>>1; dfs(node*2, tl, mid); dfs(node*2+1, mid+1, tr); for(auto it : tree4[node]) { SS[it]--; if(SS[it]==0) cnt--; } } int main() { int i, j; auto begin = chrono::high_resolution_clock::now(); scanf("%d%d%d", &N, &K, &Q); for(i=1; i<=N; i++) { int x, t, a, b; scanf("%d%d%d%d", &x, &t, &a, &b); x*=2; a=a*3-1; b=b*3+1; A[i*2-1]={x, t, a, -1}; A[i*2]={x, t, b, 1}; comp.push_back(a); comp.push_back(b); } for(i=1; i<=Q; i++) { scanf("%d%d", &query[i].l, &query[i].y); query[i].y*=3; query[i].p=i; comp.push_back(query[i].y); query[i].l*=2; } sort(comp.begin(), comp.end()); comp.erase(unique(comp.begin(), comp.end()), comp.end()); C=comp.size(); for(i=1; i<=2*N; i++) A[i].a=getcomp(A[i].a); for(i=1; i<=N; i++) update4(1, 1, C, A[i*2-1].a, A[i*2].a, A[i*2].t); for(i=1; i<=Q; i++) query[i].y=getcomp(query[i].y); for(i=1; i<=Q; i++) update3(1, 1, C, query[i].y, query[i]); sort(A+1, A+N+N+1, [&](const Data &p, const Data &q) { return p.a<q.a; }); for(i=1; i<=N+N; i++) { Data now=A[i]; int x, t, a, b; x=now.x; t=now.t; a=now.a; b=now.b; //printf("%d %d %d %d\n", x, t, a, b); if(b==-1) { if(S[t].find(x)==S[t].end()) { if(S[t].size()==0) { pushLine1(0, x); pushLine2(x, INF); } else { auto it=S[t].lower_bound(x); int l, r; if(it==S[t].end()) { l=*prev(it); pushLine2(l, l+x>>1); pushLine1(l+x>>1, x); pushLine2(x, INF); } else if(it==S[t].begin()) { r=*it; pushLine1(0, x); pushLine2(x, r+x>>1); pushLine1(r+x>>1, r); } else { r=*it, l=*prev(it); pushLine2(l, l+x>>1); pushLine1(l+x>>1, x); pushLine2(x, x+r>>1); pushLine1(x+r>>1, r); } } } S[t].insert(x); } else { S[t].erase(S[t].find(x)); if(S[t].find(x)==S[t].end()) { if(S[t].size()==0); else { auto it=S[t].lower_bound(x); int l, r; if(it==S[t].end()) { l=*prev(it); pushLine2(l, INF); } else if(it==S[t].begin()) { r=*it; pushLine1(0, r); } else { r=*it, l=*prev(it); pushLine2(l, l+r>>1); pushLine1(l+r>>1, r); } } } } } sort(lcomp.begin(), lcomp.end()); lcomp.erase(unique(lcomp.begin(), lcomp.end()), lcomp.end()); M1.resize(lcomp.size()); M2.resize(lcomp.size()); for(i=0; i<lcomp.size(); i++) MM[lcomp[i].x*INF*10ll+lcomp[i].y]=i; for(i=1; i<=N+N; i++) { Data now=A[i]; int x, t, a, b; x=now.x; t=now.t; a=now.a; b=now.b; //printf("%d %d %d %d\n", x, t, a, b); if(b==-1) { if(S[t].find(x)==S[t].end()) { if(S[t].size()==0) { pushLine1(0, x, a); pushLine2(x, INF, a); } else { auto it=S[t].lower_bound(x); int l, r; if(it==S[t].end()) { l=*prev(it); popLine2(l, INF, a); pushLine2(l, l+x>>1, a); pushLine1(l+x>>1, x, a); pushLine2(x, INF, a); } else if(it==S[t].begin()) { r=*it; popLine1(0, r, a); pushLine1(0, x, a); pushLine2(x, r+x>>1, a); pushLine1(r+x>>1, r, a); } else { r=*it, l=*prev(it); popLine2(l, l+r>>1, a); popLine1(l+r>>1, r, a); pushLine2(l, l+x>>1, a); pushLine1(l+x>>1, x, a); pushLine2(x, x+r>>1, a); pushLine1(x+r>>1, r, a); } } } S[t].insert(x); } else { S[t].erase(S[t].find(x)); if(S[t].find(x)==S[t].end()) { if(S[t].size()==0) { popLine1(0, x, a); popLine2(x, INF, a); } else { auto it=S[t].lower_bound(x); int l, r; if(it==S[t].end()) { l=*prev(it); pushLine2(l, INF, a); popLine2(l, l+x>>1, a); popLine1(l+x>>1, x, a); popLine2(x, INF, a); } else if(it==S[t].begin()) { r=*it; pushLine1(0, r, a); popLine1(0, x, a); popLine2(x, r+x>>1, a); popLine1(r+x>>1, r, a); } else { r=*it, l=*prev(it); pushLine2(l, l+r>>1, a); pushLine1(l+r>>1, r, a); popLine2(l, l+x>>1, a); popLine1(l+x>>1, x, a); popLine2(x, x+r>>1, a); popLine1(x+r>>1, r, a); } } } } } auto end = chrono::high_resolution_clock::now(); if(chrono::duration_cast<chrono::nanoseconds>(end-begin).count()>=4e9) assert(0); dfs(1, 1, C); for(i=1; i<=Q; i++) printf("%d\n", ans[i]/2); }

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

new_home.cpp: In function 'void update1(int, int, int, int, int, Line)':
new_home.cpp:67:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
new_home.cpp: In function 'void update2(int, int, int, int, int, Line)':
new_home.cpp:97:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
new_home.cpp: In function 'void update3(int, int, int, int, Query)':
new_home.cpp:127:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
new_home.cpp: In function 'void update4(int, int, int, int, int, int)':
new_home.cpp:136:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
new_home.cpp: In function 'void dfs(int, int, int)':
new_home.cpp:164:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0, j=0; i<tree3[node].size(); i++)
                   ~^~~~~~~~~~~~~~~~~~~
new_home.cpp:167:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(; j<tree1[node].size() && tree1[node][j].x<=now.l; j++)
               ~^~~~~~~~~~~~~~~~~~~
new_home.cpp:181:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0, j=0; i<tree3[node].size(); i++)
                   ~^~~~~~~~~~~~~~~~~~~
new_home.cpp:184:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(; j<tree2[node].size() && tree2[node][j].x>=now.l; j++)
               ~^~~~~~~~~~~~~~~~~~~
new_home.cpp:205:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:272:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine2(l, l+x>>1);
                                      ~^~
new_home.cpp:273:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine1(l+x>>1, x);
                                   ~^~
new_home.cpp:280:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine2(x, r+x>>1);
                                      ~^~
new_home.cpp:281:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine1(r+x>>1, r);
                                   ~^~
new_home.cpp:286:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine2(l, l+x>>1);
                                      ~^~
new_home.cpp:287:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine1(l+x>>1, x);
                                   ~^~
new_home.cpp:288:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine2(x, x+r>>1);
                                      ~^~
new_home.cpp:289:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine1(x+r>>1, r);
                                   ~^~
new_home.cpp:318:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine2(l, l+r>>1);
                                      ~^~
new_home.cpp:319:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine1(l+r>>1, r);
                                   ~^~
new_home.cpp:253:19: warning: variable 'a' set but not used [-Wunused-but-set-variable]
         int x, t, a, b;
                   ^
new_home.cpp:330:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<lcomp.size(); i++) MM[lcomp[i].x*INF*10ll+lcomp[i].y]=i;
              ~^~~~~~~~~~~~~
new_home.cpp:355:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine2(l, l+x>>1, a);
                                      ~^~
new_home.cpp:356:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine1(l+x>>1, x, a);
                                   ~^~
new_home.cpp:364:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine2(x, r+x>>1, a);
                                      ~^~
new_home.cpp:365:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine1(r+x>>1, r, a);
                                   ~^~
new_home.cpp:370:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine2(l, l+r>>1, a);
                                     ~^~
new_home.cpp:371:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine1(l+r>>1, r, a);
                                  ~^~
new_home.cpp:372:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine2(l, l+x>>1, a);
                                      ~^~
new_home.cpp:373:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine1(l+x>>1, x, a);
                                   ~^~
new_home.cpp:374:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine2(x, x+r>>1, a);
                                      ~^~
new_home.cpp:375:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine1(x+r>>1, r, a);
                                   ~^~
new_home.cpp:399:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine2(l, l+x>>1, a);
                                     ~^~
new_home.cpp:400:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine1(l+x>>1, x, a);
                                  ~^~
new_home.cpp:408:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine2(x, r+x>>1, a);
                                     ~^~
new_home.cpp:409:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine1(r+x>>1, r, a);
                                  ~^~
new_home.cpp:414:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine2(l, l+r>>1, a);
                                      ~^~
new_home.cpp:415:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine1(l+r>>1, r, a);
                                   ~^~
new_home.cpp:416:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine2(l, l+x>>1, a);
                                     ~^~
new_home.cpp:417:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine1(l+x>>1, x, a);
                                  ~^~
new_home.cpp:418:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine2(x, x+r>>1, a);
                                     ~^~
new_home.cpp:419:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine1(x+r>>1, r, a);
                                  ~^~
new_home.cpp:218:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
new_home.cpp:221:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N, &K, &Q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:225:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", &x, &t, &a, &b); x*=2; a=a*3-1; b=b*3+1;
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:234:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &query[i].l, &query[i].y); query[i].y*=3;
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...