Submission #960604

#TimeUsernameProblemLanguageResultExecution timeMemory
960604kimWall (IOI14_wall)C++17
24 / 100
877 ms17544 KiB
#include "wall.h" #include<bits/stdc++.h> using namespace std; #define eb emplace_back struct segment{ int a[1<<20],lz[1<<20][2],l0,r0; bitset<1<<20> b; void build(int i,int il,int ir){ lz[i][0]=lz[i][1]=-1; if(il==ir) return; int im=il+ir>>1; build(i<<1,il,im), build(i<<1|1,im+1,ir); } void init(int l,int r){ l0=l,r0=r; build(1,l,r); } void flush(int i,int il,int ir){ bool op=!b[i]; if(lz[i][op]!=-1){ if(il!=ir){ if(lz[i<<1][op]==-1 || op==0&&lz[i<<1][op]<lz[i][op] || op==1&&lz[i<<1][op]>lz[i][op]) lz[i<<1][op]=lz[i][op], b[i<<1]=op; if(lz[i<<1|1][op]==-1 || op==0&&lz[i<<1|1][op]<lz[i][op] || op==1&&lz[i<<1|1][op]>lz[i][op]) lz[i<<1|1][op]=lz[i][op], b[i<<1|1]=op; } else{ if(op==0) a[i]=max(a[i],lz[i][op]); else a[i]=min(a[i],lz[i][op]); } lz[i][op]=-1; } op^=1; if(lz[i][op]!=-1){ if(il!=ir){ if(lz[i<<1][op]==-1 || op==0&&lz[i<<1][op]<lz[i][op] || op==1&&lz[i<<1][op]>lz[i][op]) lz[i<<1][op]=lz[i][op], b[i<<1]=op; if(lz[i<<1|1][op]==-1 || op==0&&lz[i<<1|1][op]<lz[i][op] || op==1&&lz[i<<1|1][op]>lz[i][op]) lz[i<<1|1][op]=lz[i][op], b[i<<1|1]=op; } else{ if(op==0) a[i]=max(a[i],lz[i][op]); else a[i]=min(a[i],lz[i][op]); } lz[i][op]=-1; } } void upd(int i,int il,int ir,int l,int r,int op,int v){ flush(i,il,ir); if(l<=il&&ir<=r){ if(lz[i][op]==-1 || op==0&&lz[i][op]<v || op==1&&lz[i][op]>v) lz[i][op]=v, b[i]=op, flush(i,il,ir); return; } if(il>r||ir<l) return; int im=il+ir>>1; upd(i<<1,il,im,l,r,op,v), upd(i<<1|1,im+1,ir,l,r,op,v); } void upd(int l,int r,int op,int v){upd(1,l0,r0,l,r,op,v);} int qr(int i,int il,int ir,int x){ flush(i,il,ir); if(il==ir) return a[i]; int im=il+ir>>1; if(x<=im) return qr(i<<1,il,im,x); return qr(i<<1|1,im+1,ir,x); } int qr(int i){return qr(1,l0,r0,i);} }t; void buildWall(int n, int k, int op[], int L[], int R[], int H[], int ans[]){ vector<int> comp; for(int i=0;i<k;++i) comp.eb(L[i]),comp.eb(++R[i]); comp.eb(0),comp.eb(n); sort(comp.begin(),comp.end()); comp.erase(unique(comp.begin(),comp.end()),comp.end()); t.init(0,comp.size()); for(int i=0;i<k;++i){ L[i]=lower_bound(comp.begin(),comp.end(),L[i])-comp.begin(); R[i]=lower_bound(comp.begin(),comp.end(),R[i])-comp.begin()-1; t.upd(L[i],R[i],op[i]-1,H[i]); } for(int i=0,j=0;i+1<comp.size();++i){ for(;j<comp[i+1];++j) ans[j]=t.qr(i); } }

Compilation message (stderr)

wall.cpp: In member function 'void segment::build(int, int, int)':
wall.cpp:12:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 |   int im=il+ir>>1;
      |          ~~^~~
wall.cpp: In member function 'void segment::flush(int, int, int)':
wall.cpp:23:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   23 |     if(lz[i<<1][op]==-1 || op==0&&lz[i<<1][op]<lz[i][op] || op==1&&lz[i<<1][op]>lz[i][op]) lz[i<<1][op]=lz[i][op], b[i<<1]=op;
      |                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:23:66: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   23 |     if(lz[i<<1][op]==-1 || op==0&&lz[i<<1][op]<lz[i][op] || op==1&&lz[i<<1][op]>lz[i][op]) lz[i<<1][op]=lz[i][op], b[i<<1]=op;
      |                                                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:24:35: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   24 |     if(lz[i<<1|1][op]==-1 || op==0&&lz[i<<1|1][op]<lz[i][op] || op==1&&lz[i<<1|1][op]>lz[i][op]) lz[i<<1|1][op]=lz[i][op], b[i<<1|1]=op;
      |                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:24:70: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   24 |     if(lz[i<<1|1][op]==-1 || op==0&&lz[i<<1|1][op]<lz[i][op] || op==1&&lz[i<<1|1][op]>lz[i][op]) lz[i<<1|1][op]=lz[i][op], b[i<<1|1]=op;
      |                                                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:35:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   35 |     if(lz[i<<1][op]==-1 || op==0&&lz[i<<1][op]<lz[i][op] || op==1&&lz[i<<1][op]>lz[i][op]) lz[i<<1][op]=lz[i][op], b[i<<1]=op;
      |                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:35:66: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   35 |     if(lz[i<<1][op]==-1 || op==0&&lz[i<<1][op]<lz[i][op] || op==1&&lz[i<<1][op]>lz[i][op]) lz[i<<1][op]=lz[i][op], b[i<<1]=op;
      |                                                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:36:35: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   36 |     if(lz[i<<1|1][op]==-1 || op==0&&lz[i<<1|1][op]<lz[i][op] || op==1&&lz[i<<1|1][op]>lz[i][op]) lz[i<<1|1][op]=lz[i][op], b[i<<1|1]=op;
      |                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:36:70: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   36 |     if(lz[i<<1|1][op]==-1 || op==0&&lz[i<<1|1][op]<lz[i][op] || op==1&&lz[i<<1|1][op]>lz[i][op]) lz[i<<1|1][op]=lz[i][op], b[i<<1|1]=op;
      |                                                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp: In member function 'void segment::upd(int, int, int, int, int, int, int)':
wall.cpp:48:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   48 |    if(lz[i][op]==-1 || op==0&&lz[i][op]<v || op==1&&lz[i][op]>v) lz[i][op]=v, b[i]=op, flush(i,il,ir);
      |                        ~~~~~^~~~~~~~~~~~~
wall.cpp:48:51: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   48 |    if(lz[i][op]==-1 || op==0&&lz[i][op]<v || op==1&&lz[i][op]>v) lz[i][op]=v, b[i]=op, flush(i,il,ir);
      |                                              ~~~~~^~~~~~~~~~~~~
wall.cpp:52:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   int im=il+ir>>1;
      |          ~~^~~
wall.cpp: In member function 'int segment::qr(int, int, int, int)':
wall.cpp:59:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |   int im=il+ir>>1;
      |          ~~^~~
wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:79:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for(int i=0,j=0;i+1<comp.size();++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...