oj.uz

Submission #348689

# Submission time Handle Problem Language Result Execution time Memory
348689 2021-01-15T14:36:12 Z Kerim Dancing Elephants (IOI11_elephants) C++17
100 / 100
 7980 ms 13972 KB 
#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=500;
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[]){
	for(int i=0;i<cur;i++)
		s[i].clear(),sz[i]=0;
  	n = N; l = L; cur=0;
  	for(int i=0;i<n;i++){
  		arr[i]=X[i];
		tmp[i]=mp(X[i],i);
	}
  	sort(tmp,tmp+N);
	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){
		init(n,l,arr);
		asked=0;
	}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 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 364 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 364 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 314 ms 1516 KB Output is correct
8 Correct 364 ms 1772 KB Output is correct
9 Correct 476 ms 3052 KB Output is correct
10 Correct 589 ms 2924 KB Output is correct
11 Correct 594 ms 2924 KB Output is correct
12 Correct 1004 ms 3436 KB Output is correct
13 Correct 628 ms 2924 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 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 314 ms 1516 KB Output is correct
8 Correct 364 ms 1772 KB Output is correct
9 Correct 476 ms 3052 KB Output is correct
10 Correct 589 ms 2924 KB Output is correct
11 Correct 594 ms 2924 KB Output is correct
12 Correct 1004 ms 3436 KB Output is correct
13 Correct 628 ms 2924 KB Output is correct
14 Correct 574 ms 2284 KB Output is correct
15 Correct 564 ms 2412 KB Output is correct
16 Correct 1582 ms 3564 KB Output is correct
17 Correct 1800 ms 4460 KB Output is correct
18 Correct 1921 ms 4460 KB Output is correct
19 Correct 1113 ms 3820 KB Output is correct
20 Correct 1798 ms 4588 KB Output is correct
21 Correct 1780 ms 4460 KB Output is correct
22 Correct 1137 ms 3764 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 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 314 ms 1516 KB Output is correct
8 Correct 364 ms 1772 KB Output is correct
9 Correct 476 ms 3052 KB Output is correct
10 Correct 589 ms 2924 KB Output is correct
11 Correct 594 ms 2924 KB Output is correct
12 Correct 1004 ms 3436 KB Output is correct
13 Correct 628 ms 2924 KB Output is correct
14 Correct 574 ms 2284 KB Output is correct
15 Correct 564 ms 2412 KB Output is correct
16 Correct 1582 ms 3564 KB Output is correct
17 Correct 1800 ms 4460 KB Output is correct
18 Correct 1921 ms 4460 KB Output is correct
19 Correct 1113 ms 3820 KB Output is correct
20 Correct 1798 ms 4588 KB Output is correct
21 Correct 1780 ms 4460 KB Output is correct
22 Correct 1137 ms 3764 KB Output is correct
23 Correct 4112 ms 8360 KB Output is correct
24 Correct 4577 ms 8404 KB Output is correct
25 Correct 3237 ms 8176 KB Output is correct
26 Correct 4947 ms 7532 KB Output is correct
27 Correct 5139 ms 7524 KB Output is correct
28 Correct 1679 ms 5484 KB Output is correct
29 Correct 1464 ms 5484 KB Output is correct
30 Correct 1524 ms 5384 KB Output is correct
31 Correct 1620 ms 5376 KB Output is correct
32 Correct 4613 ms 11620 KB Output is correct
33 Correct 4424 ms 11244 KB Output is correct
34 Correct 4196 ms 11516 KB Output is correct
35 Correct 4396 ms 11500 KB Output is correct
36 Correct 3620 ms 11500 KB Output is correct
37 Correct 7980 ms 13972 KB Output is correct
38 Correct 4853 ms 11188 KB Output is correct
39 Correct 4607 ms 11528 KB Output is correct
40 Correct 5748 ms 11216 KB Output is correct
41 Correct 7002 ms 13056 KB Output is correct
42 Correct 7118 ms 13036 KB Output is correct