Submission #262539

#TimeUsernameProblemLanguageResultExecution timeMemory
262539arnold518Sweeping (JOI20_sweeping)C++14
10 / 100
1686 ms102232 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 = 1.5e6; struct Point { int x, y, p; }; struct Query { int t, p, x, y; }; int N, M, Q; Point A[MAXN+10]; Query B[MAXN+10]; int pos[MAXN+10]; struct SEG { vector<int> tree, lazy; SEG() { tree.resize(MAXN*4+10); lazy.resize(MAXN*4+10); } void busy(int node, int tl, int tr) { tree[node]=max(tree[node], lazy[node]); if(tl!=tr) { lazy[node*2]=max(lazy[node*2], lazy[node]); lazy[node*2+1]=max(lazy[node*2+1], lazy[node]); } lazy[node]=0; } void update(int node, int tl, int tr, int l, int r, int k) { busy(node, tl, tr); if(r<tl || tr<l) return; if(l<=tl && tr<=r) { lazy[node]=k; busy(node, tl, tr); return; } int mid=tl+tr>>1; update(node*2, tl, mid, l, r, k); update(node*2+1, mid+1, tr, l, r, k); } void update2(int node, int tl, int tr, int p, int k) { busy(node, tl, tr); if(tl==tr) { tree[node]=k; return; } int mid=tl+tr>>1; if(p<=mid) update2(node*2, tl, mid, p ,k); else update2(node*2+1, mid+1, tr, p, k); } int query(int node, int tl, int tr, int p) { busy(node, tl, tr); if(tl==tr) return tree[node]; int mid=tl+tr>>1; if(p<=mid) return query(node*2, tl, mid, p); else return query(node*2+1, mid+1, tr, p); } }seg; int main() { scanf("%d%d%d", &N, &M, &Q); for(int i=1; i<=M; i++) scanf("%d%d", &A[i].x, &A[i].y), A[i].p=i; for(int i=1; i<=Q; i++) { scanf("%d", &B[i].t); if(B[i].t==1) scanf("%d", &B[i].p); else if(B[i].t==2) scanf("%d", &B[i].x); else if(B[i].t==3) scanf("%d", &B[i].x); else if(B[i].t==4) { scanf("%d%d", &B[i].x, &B[i].y); B[i].p=++M; A[M]={B[i].x, B[i].y, M}; } } sort(A+1, A+M+1, [&](const Point &p, const Point &q) { return p.y<q.y; }); for(int i=1; i<=M; i++) pos[A[i].p]=i; for(int i=1; i<=M; i++) seg.update2(1, 1, M, i, A[i].x); for(int i=1; i<=Q; i++) { if(B[i].t==1) { printf("%d %d\n", seg.query(1, 1, M, pos[B[i].p]), A[pos[B[i].p]].y); } else if(B[i].t==2) { int lo=0, hi=M+1; while(lo+1<hi) { int mid=lo+hi>>1; if(A[mid].y<=B[i].x) lo=mid; else hi=mid; } seg.update(1, 1, M, 1, lo, N-B[i].x); } else if(B[i].t==4) { seg.update2(1, 1, M, pos[B[i].p], B[i].x); } } }

Compilation message (stderr)

sweeping.cpp: In member function 'void SEG::update(int, int, int, int, int, int)':
sweeping.cpp:56:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |   int mid=tl+tr>>1;
      |           ~~^~~
sweeping.cpp: In member function 'void SEG::update2(int, int, int, int, int)':
sweeping.cpp:65:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |   int mid=tl+tr>>1;
      |           ~~^~~
sweeping.cpp: In member function 'int SEG::query(int, int, int, int)':
sweeping.cpp:74:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |   int mid=tl+tr>>1;
      |           ~~^~~
sweeping.cpp: In function 'int main()':
sweeping.cpp:114:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |     int mid=lo+hi>>1;
      |             ~~^~~
sweeping.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |  scanf("%d%d%d", &N, &M, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:83:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |  for(int i=1; i<=M; i++) scanf("%d%d", &A[i].x, &A[i].y), A[i].p=i;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   87 |   scanf("%d", &B[i].t);
      |   ~~~~~^~~~~~~~~~~~~~~
sweeping.cpp:88:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   88 |   if(B[i].t==1) scanf("%d", &B[i].p);
      |                 ~~~~~^~~~~~~~~~~~~~~
sweeping.cpp:89:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   89 |   else if(B[i].t==2) scanf("%d", &B[i].x);
      |                      ~~~~~^~~~~~~~~~~~~~~
sweeping.cpp:90:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |   else if(B[i].t==3) scanf("%d", &B[i].x);
      |                      ~~~~~^~~~~~~~~~~~~~~
sweeping.cpp:93:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |    scanf("%d%d", &B[i].x, &B[i].y);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#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...