Submission #356054

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
356054	2021-01-23T06:42:15 Z	tengiz05	Dancing Elephants (IOI11_elephants)	C++17	100 / 100	4277 ms	14700 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=1000;
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	364 KB	Output is correct
2	Correct	1 ms	492 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	364 KB	Output is correct
2	Correct	1 ms	492 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	364 KB	Output is correct
2	Correct	1 ms	492 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	485 ms	2540 KB	Output is correct
8	Correct	494 ms	2780 KB	Output is correct
9	Correct	479 ms	4588 KB	Output is correct
10	Correct	465 ms	4204 KB	Output is correct
11	Correct	465 ms	4076 KB	Output is correct
12	Correct	927 ms	4788 KB	Output is correct
13	Correct	471 ms	3980 KB	Output is correct

Subtask #4
47.0 / 47.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	492 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	485 ms	2540 KB	Output is correct
8	Correct	494 ms	2780 KB	Output is correct
9	Correct	479 ms	4588 KB	Output is correct
10	Correct	465 ms	4204 KB	Output is correct
11	Correct	465 ms	4076 KB	Output is correct
12	Correct	927 ms	4788 KB	Output is correct
13	Correct	471 ms	3980 KB	Output is correct
14	Correct	658 ms	3776 KB	Output is correct
15	Correct	739 ms	3692 KB	Output is correct
16	Correct	1665 ms	5220 KB	Output is correct
17	Correct	1528 ms	6380 KB	Output is correct
18	Correct	1698 ms	6400 KB	Output is correct
19	Correct	839 ms	5996 KB	Output is correct
20	Correct	1508 ms	6252 KB	Output is correct
21	Correct	1432 ms	6652 KB	Output is correct
22	Correct	725 ms	5356 KB	Output is correct

Subtask #5
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	492 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	485 ms	2540 KB	Output is correct
8	Correct	494 ms	2780 KB	Output is correct
9	Correct	479 ms	4588 KB	Output is correct
10	Correct	465 ms	4204 KB	Output is correct
11	Correct	465 ms	4076 KB	Output is correct
12	Correct	927 ms	4788 KB	Output is correct
13	Correct	471 ms	3980 KB	Output is correct
14	Correct	658 ms	3776 KB	Output is correct
15	Correct	739 ms	3692 KB	Output is correct
16	Correct	1665 ms	5220 KB	Output is correct
17	Correct	1528 ms	6380 KB	Output is correct
18	Correct	1698 ms	6400 KB	Output is correct
19	Correct	839 ms	5996 KB	Output is correct
20	Correct	1508 ms	6252 KB	Output is correct
21	Correct	1432 ms	6652 KB	Output is correct
22	Correct	725 ms	5356 KB	Output is correct
23	Correct	2965 ms	13336 KB	Output is correct
24	Correct	3373 ms	13204 KB	Output is correct
25	Correct	2033 ms	13328 KB	Output is correct
26	Correct	3072 ms	12568 KB	Output is correct
27	Correct	3512 ms	12420 KB	Output is correct
28	Correct	2603 ms	5400 KB	Output is correct
29	Correct	2518 ms	5356 KB	Output is correct
30	Correct	2415 ms	5416 KB	Output is correct
31	Correct	2407 ms	5416 KB	Output is correct
32	Correct	1999 ms	12000 KB	Output is correct
33	Correct	2122 ms	11328 KB	Output is correct
34	Correct	2054 ms	12268 KB	Output is correct
35	Correct	2091 ms	12500 KB	Output is correct
36	Correct	2405 ms	11984 KB	Output is correct
37	Correct	2944 ms	14700 KB	Output is correct
38	Correct	2179 ms	11228 KB	Output is correct
39	Correct	2323 ms	12244 KB	Output is correct
40	Correct	2718 ms	11116 KB	Output is correct
41	Correct	4258 ms	13100 KB	Output is correct
42	Correct	4277 ms	13360 KB	Output is correct

Submission #356054

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