제출 #171242

#제출 시각아이디문제언어결과실행 시간메모리
171242arnold518새 집 (APIO18_new_home)C++14
47 / 100
5143 ms693044 KiB
#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); } }; 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]; //================================================== unordered_map<ll, 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); ll q=p.x*INF*10ll+p.y; 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); ll q=p.x*INF*10ll+p.y; M1[q].second--; if(M1[q].second==0) update1(1, 1, C, M1[q].first, t, p); } //================================================== unordered_map<ll, 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); ll q=p.x*INF*10ll+p.y; 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); ll q=p.x*INF*10ll+p.y; 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; 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, 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); } } } } } 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:44: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:74: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:104: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:113: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:141:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0, j=0; i<tree3[node].size(); i++)
                   ~^~~~~~~~~~~~~~~~~~~
new_home.cpp:144: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:158:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0, j=0; i<tree3[node].size(); i++)
                   ~^~~~~~~~~~~~~~~~~~~
new_home.cpp:161: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:182:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:249:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine2(l, l+x>>1, a);
                                      ~^~
new_home.cpp:250:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine1(l+x>>1, x, a);
                                   ~^~
new_home.cpp:258:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine2(x, r+x>>1, a);
                                      ~^~
new_home.cpp:259:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine1(r+x>>1, r, a);
                                   ~^~
new_home.cpp:264:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine2(l, l+r>>1, a);
                                     ~^~
new_home.cpp:265:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine1(l+r>>1, r, a);
                                  ~^~
new_home.cpp:266:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine2(l, l+x>>1, a);
                                      ~^~
new_home.cpp:267:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine1(l+x>>1, x, a);
                                   ~^~
new_home.cpp:268:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine2(x, x+r>>1, a);
                                      ~^~
new_home.cpp:269:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine1(x+r>>1, r, a);
                                   ~^~
new_home.cpp:293:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine2(l, l+x>>1, a);
                                     ~^~
new_home.cpp:294:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine1(l+x>>1, x, a);
                                  ~^~
new_home.cpp:302:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine2(x, r+x>>1, a);
                                     ~^~
new_home.cpp:303:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine1(r+x>>1, r, a);
                                  ~^~
new_home.cpp:308:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine2(l, l+r>>1, a);
                                      ~^~
new_home.cpp:309:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine1(l+r>>1, r, a);
                                   ~^~
new_home.cpp:310:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine2(l, l+x>>1, a);
                                     ~^~
new_home.cpp:311:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine1(l+x>>1, x, a);
                                  ~^~
new_home.cpp:312:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine2(x, x+r>>1, a);
                                     ~^~
new_home.cpp:313:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine1(x+r>>1, r, a);
                                  ~^~
new_home.cpp:195:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
new_home.cpp:197: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:201: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:210: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...