Submission #348720

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
348720	2021-01-15T15:16:43 Z	Kerim	Dancing Elephants (IOI11_elephants)	C++17	100 / 100	3786 ms	10220 KB

elephants

#include "elephants.h"
#include "bits/stdc++.h"
#define MAXN 150009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int n,l,arr[MAXN],asked=1,cur;
int sz[MAXN],where[MAXN];
PII tmp[MAXN];
const int BLOK=700;
vector<PII>dp[MAXN/BLOK+3],s[MAXN/BLOK+3];
void build(int block){
	int p=sz[block]-1;
	for(int i=sz[block]-1;i>=0;i--){
		while(s[block][i].ff+l<s[block][p].ff)p--;
		if(p+1<sz[block])dp[block][i]=mp(dp[block][p+1].ff+1,dp[block][p+1].ss);
		else dp[block][i]=mp(0,i);
	}
}
int query(){
	int last=-1,ans=0;
	for(int i=0;i<cur;i++)
		if(sz[i]){
			int pos=upper_bound(all(s[i]),mp(last,INF))-s[i].begin();
			if(pos<sz[i]){
				if(dp[i][pos].ff)
					ans+=dp[i][pos].ff,pos=dp[i][pos].ss;
				last=s[i][pos].ff+l;ans++;	
			}
		}
	return ans;
}
void init(int N, int L, int X[]){
  	n = N; l = L; 
  	if(asked){
	  	for(int i=0;i<n;i++){
	  		arr[i]=X[i];
			tmp[i]=mp(X[i],i);
		}
	}
	else{
		int pos=0;
		for(int i=0;i<cur;i++){
			tr(it,s[i])
				tmp[pos++]=*it;
			s[i].clear();sz[i]=0;	
		}
	}
	cur=0;
	for(int i=0;i<n;i++){
		where[tmp[i].ss]=cur;
		s[cur].pb(tmp[i]);
		sz[cur]++;
		if((i+1)%BLOK==0)
			cur++;
	}if(n%BLOK!=0)cur++;
	for(int i=0;i<cur;i++){
		dp[i].resize(sz[i]);
		build(i);
	}
}
void rem(int block,PII val){
	for(int i=0;i<int(s[block].size());i++)
		if(s[block][i]==val){
			s[block].erase(s[block].end()-(sz[block]-i));
			break;
		}
	sz[block]--;dp[block].ppb();
	build(block);
}
void add(int block){
	sz[block]++;dp[block].pb(mp(-1,-1));
	for(int i=sz[block]-1;i>0;i--)
		if(s[block][i].ff<s[block][i-1].ff)
			swap(s[block][i],s[block][i-1]);
	build(block);
}
int update(int pos, int val){
	if(asked%BLOK==0){
		asked=0;
		init(n,l,arr);
	}asked++;
	rem(where[pos],mp(arr[pos],pos));
	arr[pos]=val;
	for(int i=0;i+1<cur;i++)
		if(s[i+1].size() and s[i+1][0].ff>val){
			s[i].pb(mp(val,pos));where[pos]=i;add(i);
			return query();
		}
	s[cur-1].pb(mp(val,pos));where[pos]=cur-1;add(cur-1);
	return query();
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	508 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct

Subtask #2
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	508 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct

Subtask #3
24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	508 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	361 ms	1516 KB	Output is correct
8	Correct	392 ms	1900 KB	Output is correct
9	Correct	402 ms	3052 KB	Output is correct
10	Correct	346 ms	3052 KB	Output is correct
11	Correct	381 ms	2924 KB	Output is correct
12	Correct	737 ms	3308 KB	Output is correct
13	Correct	367 ms	3052 KB	Output is correct

Subtask #4
47.0 / 47.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	508 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	361 ms	1516 KB	Output is correct
8	Correct	392 ms	1900 KB	Output is correct
9	Correct	402 ms	3052 KB	Output is correct
10	Correct	346 ms	3052 KB	Output is correct
11	Correct	381 ms	2924 KB	Output is correct
12	Correct	737 ms	3308 KB	Output is correct
13	Correct	367 ms	3052 KB	Output is correct
14	Correct	504 ms	2156 KB	Output is correct
15	Correct	596 ms	2284 KB	Output is correct
16	Correct	1342 ms	3600 KB	Output is correct
17	Correct	1254 ms	4492 KB	Output is correct
18	Correct	1401 ms	4460 KB	Output is correct
19	Correct	768 ms	4076 KB	Output is correct
20	Correct	1252 ms	4588 KB	Output is correct
21	Correct	1188 ms	4536 KB	Output is correct
22	Correct	702 ms	4008 KB	Output is correct

Subtask #5
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	508 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	361 ms	1516 KB	Output is correct
8	Correct	392 ms	1900 KB	Output is correct
9	Correct	402 ms	3052 KB	Output is correct
10	Correct	346 ms	3052 KB	Output is correct
11	Correct	381 ms	2924 KB	Output is correct
12	Correct	737 ms	3308 KB	Output is correct
13	Correct	367 ms	3052 KB	Output is correct
14	Correct	504 ms	2156 KB	Output is correct
15	Correct	596 ms	2284 KB	Output is correct
16	Correct	1342 ms	3600 KB	Output is correct
17	Correct	1254 ms	4492 KB	Output is correct
18	Correct	1401 ms	4460 KB	Output is correct
19	Correct	768 ms	4076 KB	Output is correct
20	Correct	1252 ms	4588 KB	Output is correct
21	Correct	1188 ms	4536 KB	Output is correct
22	Correct	702 ms	4008 KB	Output is correct
23	Correct	2996 ms	8972 KB	Output is correct
24	Correct	3313 ms	9024 KB	Output is correct
25	Correct	2075 ms	8560 KB	Output is correct
26	Correct	2239 ms	8044 KB	Output is correct
27	Correct	2743 ms	8044 KB	Output is correct
28	Correct	1824 ms	2412 KB	Output is correct
29	Correct	1826 ms	2416 KB	Output is correct
30	Correct	1859 ms	2416 KB	Output is correct
31	Correct	1855 ms	2416 KB	Output is correct
32	Correct	2298 ms	8044 KB	Output is correct
33	Correct	2114 ms	8044 KB	Output is correct
34	Correct	1940 ms	8076 KB	Output is correct
35	Correct	1788 ms	8044 KB	Output is correct
36	Correct	1883 ms	7916 KB	Output is correct
37	Correct	2851 ms	10220 KB	Output is correct
38	Correct	2202 ms	8044 KB	Output is correct
39	Correct	2130 ms	7916 KB	Output is correct
40	Correct	2595 ms	7916 KB	Output is correct
41	Correct	3726 ms	9200 KB	Output is correct
42	Correct	3786 ms	9196 KB	Output is correct

Submission #348720

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 16.0 / 16.0

Subtask #3 24.0 / 24.0

Subtask #4 47.0 / 47.0

Subtask #5 3.0 / 3.0

Subtask #1
10.0 / 10.0

Subtask #2
16.0 / 16.0

Subtask #3
24.0 / 24.0

Subtask #4
47.0 / 47.0

Subtask #5
3.0 / 3.0