Submission #500809

#TimeUsernameProblemLanguageResultExecution timeMemory
500809andrei_boacaWeirdtree (RMI21_weirdtree)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #include "weirdtree.h" #include "grader.cpp" using namespace std; typedef long long ll; int n; struct date { ll max1,max2,fr1,suma,lazy; } arb[1500005]; ll need=0; void build(int nod,int st,int dr) { arb[nod].fr1=dr-st+1; arb[nod].max1=0; arb[nod].max2=0; arb[nod].suma=0; arb[nod].lazy=0; if(st==dr) return; int mij=(st+dr)/2; build(nod*2,st,mij); build(nod*2+1,mij+1,dr); } date combine(date a, date b) { date rez={0,0,0,0,0}; rez.suma=(a.suma+b.suma); rez.max1=max(a.max1,b.max1); if(a.max1==b.max1) { rez.fr1=a.fr1+b.fr1; rez.max2=max(a.max2,b.max2); } else if(a.max1>b.max1) { rez.fr1=a.fr1; rez.max2=max(a.max2,b.max1); } else if(a.max1<b.max1) { rez.fr1=b.fr1; rez.max2=max(a.max1,b.max2); } return rez; } void prop(int nod) { int val=arb[nod].lazy; for(int i=nod*2;i<=nod*2+1;i++) if(arb[i].max1-val==arb[nod].max1) { arb[i].max1-=val; arb[i].lazy+=val; arb[i].suma-=val*arb[i].fr1; } } void cutupd(int nod,int st,int dr,int a,int b,int val,int extra) { if(st!=dr&&arb[nod].lazy!=0) prop(nod); arb[nod].lazy=0; int mij=(st+dr)/2; date x=arb[nod]; bool kk=0; if(x.max1==997825028) kk=1; if(st>=a&&dr<=b) { if(extra==x.fr1) { val++; extra=0; } if(st==dr) { arb[nod].max1=max(arb[nod].max1-val,0LL); arb[nod].suma=arb[nod].max1; arb[nod].fr1=1; return; } if(x.max1-val>x.max2&&extra==0) { bool ok=0; if(x.max1==997949551) ok=1; arb[nod].max1-=val; arb[nod].lazy+=val; arb[nod].suma-=val*arb[nod].fr1; return; } else if(x.max1-val==x.max2&&extra==0) { if(arb[nod*2].max1==x.max1) cutupd(nod*2,st,mij,a,b,val,extra); if(arb[nod*2+1].max1==x.max1) cutupd(nod*2+1,mij+1,dr,a,b,val,extra); arb[nod]=combine(arb[nod*2],arb[nod*2+1]); return; } if(arb[nod*2].max1==x.max1) { int put=min(extra*1LL,arb[nod*2].fr1); cutupd(nod*2,st,mij,a,b,val,put); if(arb[nod*2+1].max1==x.max1) cutupd(nod*2+1,mij+1,dr,a,b,val,extra-put); arb[nod]=combine(arb[nod*2],arb[nod*2+1]); return; } cutupd(nod*2+1,mij+1,dr,a,b,val,extra); arb[nod]=combine(arb[nod*2],arb[nod*2+1]); return; } if(a<=mij&&arb[nod*2].max1>=need) cutupd(nod*2,st,mij,a,b,val,extra); if(b>mij&&arb[nod*2+1].max1>=need) cutupd(nod*2+1,mij+1,dr,a,b,val,extra); arb[nod]=combine(arb[nod*2],arb[nod*2+1]); } void magicupd(int nod,int st,int dr,int poz,int val) { if(st!=dr&&arb[nod].lazy!=0) prop(nod); arb[nod].lazy=0; if(st==poz&&dr==poz) { arb[nod].suma=val; arb[nod].max1=val; arb[nod].fr1=1; arb[nod].max2=0; arb[nod].lazy=0; return; } int mij=(st+dr)/2; if(poz<=mij) magicupd(nod*2,st,mij,poz,val); if(poz>mij) magicupd(nod*2+1,mij+1,dr,poz,val); arb[nod]=combine(arb[nod*2],arb[nod*2+1]); } date query(int nod,int st,int dr,int a, int b) { if(st!=dr&&arb[nod].lazy!=0) prop(nod); arb[nod].lazy=0; if(st>=a&&dr<=b) return arb[nod]; date rez={0,0,0,0,0}; ll mij=(st+dr)/2; if(a<=mij) { date x=query(nod*2,st,mij,a,b); rez=combine(rez,x); } if(b>mij) { date x=query(nod*2+1,mij+1,dr,a,b); rez=combine(rez,x); } return rez; } void initialise(int N, int Q, int h[]) { n=N; build(1,1,n); for(int i=1;i<=n;i++) magicupd(1,1,n,i,h[i]); } void cut(int l, int r, int k) { while(k>0) { date x=query(1,1,n,l,r); bool ok=0; if(x.max2==997825028) ok=1; ll fr1=x.fr1; ll max1=x.max1; need=x.max1; if(max1==0) break; ll max2=x.max2; if((max1-max2)*fr1<=k) { cutupd(1,1,n,l,r,max1-max2,0); k-=(max1-max2)*fr1; continue; } ll val=k/fr1; ll extra=k%fr1; cutupd(1,1,n,l,r,val,extra); k=0; break; } } void magic(int i, int x) { magicupd(1,1,n,i,x); } long long int inspect(int l, int r) { return query(1,1,n,l,r).suma; }

Compilation message (stderr)

weirdtree.cpp: In function 'void cutupd(int, int, int, int, int, int, int)':
weirdtree.cpp:84:18: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   84 |             bool ok=0;
      |                  ^~
weirdtree.cpp:65:10: warning: variable 'kk' set but not used [-Wunused-but-set-variable]
   65 |     bool kk=0;
      |          ^~
weirdtree.cpp: In function 'void cut(int, int, int)':
weirdtree.cpp:172:14: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
  172 |         bool ok=0;
      |              ^~
/usr/bin/ld: /tmp/cc44YKju.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cchQoecx.o:weirdtree.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status