Submission #1004770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004770		vjudge1	Dancing Elephants (IOI11_elephants)	C++17	Compilation error	0 ms	0 KiB

elephants

#include<bits/stdc++.h>
using namespace std;
const int len=400,maxn=150005,maxg=400;
int n,m,L,id,dest,teamn,x[maxn],belong[maxn],dp[maxn],nxt[maxn],rp[maxg],cnt[maxg];
set<pair<int,int> > S;
void build(){
	teamn=0;
	pair<int,int> lst;
	for(auto p=S.begin();(p++)!=S.end();p++){
		p--;
		pair<int,int> j=(*p);
		int i=j.second;
		if(cnt[teamn]>maxg&&j.first!=lst.first){
			rp[belong[lst.second]]=x[i];
			teamn++;
		}
		cnt[teamn]++;
		belong[i]=teamn;
		lst=j;
	}
	//printf(":)");
	rp[teamn]=x[(*(S.rbegin()--)).second];
	teamn++;
	for(auto p=S.rbegin();p!=S.rend();p++){
		if(p==S.rbegin()) continue;
		int i=(*p).second;
		//printf("(%d)",i);
		if(x[i]+L>=rp[belong[i]]){
			dp[i]=1;
			nxt[i]=(*S.upper_bound(make_pair(x[i]+L,n))).second;
		}
		else{
			int nxtp=(*S.upper_bound(make_pair(x[i]+L,n))).second;
			dp[i]=dp[nxtp]+1;
			nxt[i]=nxt[nxtp];
		}
	}
}
int main(){
	scanf("%d%d%d",&n,&L,&m);
	for(int i=0;i<n;i++){
		scanf("%d",&x[i]);
		S.insert(make_pair(x[i],i));
	}
	S.insert(make_pair(2e9+5,n));
	build();
	while(m--){
		scanf("%d%d",&id,&dest);
		int bl1=belong[id];
		S.erase(make_pair(x[id],id));
		cnt[belong[id]]--;
		x[id]=dest;
		S.insert(make_pair(x[id],id));
		int belonging=upper_bound(rp,rp+teamn,x[id])-rp;
		if(belonging>=teamn){
			belonging=teamn-1;
			rp[belonging]=x[id];
		}
		belong[id]=belonging;
		cnt[belong[id]]++;
		if(cnt[belong[id]]>2*maxg) build();
		else{
			for(auto p=S.upper_bound(make_pair(rp[bl1],0));p!=S.lower_bound(make_pair((bl1==0)?0:rp[bl1-1]+1,0));p--){
				if(p==S.upper_bound(make_pair(rp[bl1],0))) continue;
				int i=(*p).second;
				if(x[i]+L>=rp[belong[i]]){
					dp[i]=1;
					nxt[i]=(*S.upper_bound(make_pair(x[i]+L,n))).second;
				}
				else{
					int nxtp=(*S.upper_bound(make_pair(x[i]+L,n))).second;
					dp[i]=dp[nxtp]+1;
					nxt[i]=nxt[nxtp];
				}
			}
			auto r=S.lower_bound(make_pair((bl1==0)?0:rp[bl1-1]+1,0));
			int l=(*r).second;
			if(x[l]+L>=rp[belong[l]]){
				dp[l]=1;
				nxt[l]=(*S.upper_bound(make_pair(x[l]+L,n))).second;
			}
			else{
				int nxtp=(*S.upper_bound(make_pair(x[l]+L,n))).second;
				dp[l]=dp[nxtp]+1;
				nxt[l]=nxt[nxtp];
			}
			bl1=belong[id];
			for(auto p=S.upper_bound(make_pair(rp[bl1],0));p!=S.lower_bound(make_pair((bl1==0)?0:rp[bl1-1]+1,0));p--){
				if(p==S.upper_bound(make_pair(rp[bl1],0))) continue;
				int i=(*p).second;
				if(x[i]+L>=rp[belong[i]]){
					dp[i]=1;
					nxt[i]=(*S.upper_bound(make_pair(x[i]+L,n))).second;
				}
				else{
					int nxtp=(*S.upper_bound(make_pair(x[i]+L,n))).second;
					dp[i]=dp[nxtp]+1;
					nxt[i]=nxt[nxtp];
				}
			}
			auto q=S.lower_bound(make_pair((bl1==0)?0:rp[bl1-1]+1,0));
			int j=(*q).second;
			if(x[j]+L>=rp[belong[j]]){
				dp[j]=1;
				nxt[j]=(*S.upper_bound(make_pair(x[j]+L,n))).second;
			}
			else{
				int nxtp=(*S.upper_bound(make_pair(x[j]+L,n))).second;
				dp[j]=dp[nxtp]+1;
				nxt[j]=nxt[nxtp];
			}
		}
		int pos=(*S.begin()).second,ans=0;
		while(pos<((*S.rbegin()).second)){
			ans+=dp[pos];
			pos=nxt[pos];
		}
		printf("%d\n",ans);
	}
	return 0;
} 

Compilation message (stderr)

elephants.cpp: In function 'int main()':
elephants.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  scanf("%d%d%d",&n,&L,&m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
elephants.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   scanf("%d",&x[i]);
      |   ~~~~~^~~~~~~~~~~~
elephants.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   scanf("%d%d",&id,&dest);
      |   ~~~~~^~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cc8CcaOf.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccgT3ali.o:elephants.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc8CcaOf.o: in function `main':
grader.cpp:(.text.startup+0x27): undefined reference to `init(int, int, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x56): undefined reference to `update(int, int)'
collect2: error: ld returned 1 exit status