Submission #322106

#	Time	Username	Problem	Language	Result	Execution time	Memory
322106		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[])
  	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 | }
      | ^