Submission #322106

#TimeUsernameProblemLanguageResultExecution timeMemory
322106sean9892Dancing Elephants (IOI11_elephants)C++14
Compilation error
0 ms0 KiB
#pragma GCC optimize ("O3") #pragma GCC optimize ("Ofast") #include<bits/stdc++.h> using namespace std; const int sq=400; int N,L,G; int arr[160000]; int inp[160000]; int con; struct Bucket{ int brr[sq*2],cnt[sq*2],lst[sq*2]; int sz; void f(){ int k=sz; for(int i=sz;i>0;i--){ while(i<k&&brr[i]+L<brr[k-1])k--; if(brr[i]+L>=brr[sz]){ cnt[i]=1; lst[i]=brr[i]+L; } else{ cnt[i]=cnt[k]+1; lst[i]=lst[k]; } } } }; Bucket gr[sq]; void rel(){ con=0; int idx=0; for(int i=1;i<=G;i++){ for(int j=1;j<=gr[i].sz;j++){ idx++; arr[idx]=gr[i].brr[j]; } gr[i].sz=0; } G=1; for(int i=1;i<=idx;i++){ if(gr[G].sz==sq-10)G++; gr[G].sz++; gr[G].brr[gr[G].sz]=arr[i]; } for(int i=1;i<=G;i++){ gr[i].f(); } } void ins(int now){ int gi,id; for(gi=1;gi<G;gi++){ if(now<gr[gi].brr[gr[gi].sz])break; } for(id=1;id<=gr[gi].sz;id++){ if(now<gr[gi].brr[id])break; } for(int i=gr[gi].sz;i>=id;i--){ gr[gi].brr[i+1]=gr[gi].brr[i]; } gr[gi].sz++; gr[gi].brr[id]=now; gr[gi].f(); } int del(int now){ int gi; for(gi=1;gi<G;gi++){ if(gr[gi].brr[1]<=now&&gr[gi+1].brr[1]>now)break; } for(int i=1;i<=gr[gi].sz;i++){ if(gr[gi].brr[i]==now){ for(;i<gr[gi].sz;i++){ gr[gi].brr[i]=gr[gi].brr[i+1]; } gr[gi].sz--; break; } } gr[gi].f(); return gr[gi].sz; } int query(){ int res=gr[1].cnt[1]; int lst=gr[1].lst[1]; for(int i=2;i<=G;i++){ if(!gr[i].sz||gr[i].brr[gr[i].sz]<=lst)continue; int l=1,r=gr[i].sz; int now; while(l<=r){ int m=l+r>>1; if(gr[i].brr[m]>lst){ now=m; r=m-1; } else{ l=m+1; } res+=gr[i].cnt[now]; lst=gr[i].lst[now]; } } return res; } int update(int i,int y){ con++; if(con==sq-10)rel(); if(!del(inp[i]))rel(); inp[i]=y; ins(y); return query(); } void init(int n,int l,int x[]) int N=n;int L=l; G=1; for(int i=0;i<N;i++){ inp[i]=x[i]; if(gr[G].sz==sq-10)G++; gr[G].sz++; gr[G].brr[gr[G].sz]=inp[i]; } for(int i=1;i<=G;i++){ gr[i].f(); } }

Compilation message (stderr)

elephants.cpp: In function 'int query()':
elephants.cpp:97:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |    int m=l+r>>1;
      |          ~^~
elephants.cpp: At global scope:
elephants.cpp:122:4: error: expected initializer before 'int'
  122 |    int N=n;int L=l;
      |    ^~~
elephants.cpp:122:16: error: redefinition of 'int L'
  122 |    int N=n;int L=l;
      |                ^
elephants.cpp:8:7: note: 'int L' previously declared here
    8 | int N,L,G;
      |       ^
elephants.cpp:122:18: error: 'l' was not declared in this scope
  122 |    int N=n;int L=l;
      |                  ^
elephants.cpp:123:2: error: 'G' does not name a type
  123 |  G=1;
      |  ^
elephants.cpp:124:2: error: expected unqualified-id before 'for'
  124 |  for(int i=0;i<N;i++){
      |  ^~~
elephants.cpp:124:14: error: 'i' does not name a type
  124 |  for(int i=0;i<N;i++){
      |              ^
elephants.cpp:124:18: error: 'i' does not name a type
  124 |  for(int i=0;i<N;i++){
      |                  ^
elephants.cpp:130:2: error: expected unqualified-id before 'for'
  130 |  for(int i=1;i<=G;i++){
      |  ^~~
elephants.cpp:130:14: error: 'i' does not name a type
  130 |  for(int i=1;i<=G;i++){
      |              ^
elephants.cpp:130:19: error: 'i' does not name a type
  130 |  for(int i=1;i<=G;i++){
      |                   ^
elephants.cpp:133:1: error: expected declaration before '}' token
  133 | }
      | ^