Submission #322107

#	Time	Username	Problem	Language	Result	Execution time	Memory
322107		sean9892	Dancing Elephants (IOI11_elephants)	C++14	Compilation error	0 ms	0 KiB

elephants

#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[])
  	N=n;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 'N'
  122 |    N=n;L=l;G=1;
      |    ^
elephants.cpp:122:8: error: 'L' does not name a type
  122 |    N=n;L=l;G=1;
      |        ^
elephants.cpp:122:12: error: 'G' does not name a type
  122 |    N=n;L=l;G=1;
      |            ^
elephants.cpp:123:2: error: expected unqualified-id before 'for'
  123 |  for(int i=0;i<N;i++){
      |  ^~~
elephants.cpp:123:14: error: 'i' does not name a type
  123 |  for(int i=0;i<N;i++){
      |              ^
elephants.cpp:123:18: error: 'i' does not name a type
  123 |  for(int i=0;i<N;i++){
      |                  ^
elephants.cpp:129:2: error: expected unqualified-id before 'for'
  129 |  for(int i=1;i<=G;i++){
      |  ^~~
elephants.cpp:129:14: error: 'i' does not name a type
  129 |  for(int i=1;i<=G;i++){
      |              ^
elephants.cpp:129:19: error: 'i' does not name a type
  129 |  for(int i=1;i<=G;i++){
      |                   ^
elephants.cpp:132:1: error: expected declaration before '}' token
  132 | }
      | ^