oj.uz

Submission #920349

# Submission time Handle Problem Language Result Execution time Memory
920349 2024-02-02T13:30:13 Z Lalic Dancing Elephants (IOI11_elephants) C++17
100 / 100
 2343 ms 18004 KB 
#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 15e4+10;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9+7;
const int blockSize = 400;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int bucket[405][2*405+10], qtd[405][2*405+10], fim[405][2*405+10];
int arr[MAXN], aux[MAXN], bucketSize[405];
int n, lim, cnt;

int getBucketId(int val){
	int l=1, r=(n-1)/blockSize, best=0;
	if(!bucketSize[(n-1)/blockSize]) r--;
	while(l<=r){
		int mid=(l+r)>>1;
		if(bucket[mid][0]<=val){
			best=mid;
			l=mid+1;
		}
		else r=mid-1;
	}
	return best;
}

void calcRes(int b){
	int id=bucketSize[b];
	for(int i=bucketSize[b]-1;i>=0;i--){
		while(bucket[b][id-1]>bucket[b][i]+lim) id--;
		if(id==bucketSize[b]){
			qtd[b][i]=1;
			fim[b][i]=bucket[b][i]+lim;
		}
		else{
			qtd[b][i]=qtd[b][id]+1;
			fim[b][i]=fim[b][id];
		}
	}
}

void addToBucket(int val){
	int b=getBucketId(val);
	//cout << "val = " << val << "\t" << "id = " << b << "\n";
	int id=0;
	while(id<bucketSize[b] && bucket[b][id]<val) id++;
	for(int i=bucketSize[b];i>=id+1;i--) bucket[b][i]=bucket[b][i-1];
	bucket[b][id]=val;
	bucketSize[b]++;
	calcRes(b);
}

void removeFromBucket(int val){
	int b=getBucketId(val);
	//cout << "val = " << val << "\t" << "id = " << b << "\n";
	int id=0;
	while(id<bucketSize[b] && bucket[b][id]<val) id++;
	for(int i=id;i<bucketSize[b]-1;i++) bucket[b][i]=bucket[b][i+1];
	bucketSize[b]--;
	calcRes(b);
}

void recalculate(){
	int id=0;
	for(int i=0;i<=(n-1)/blockSize;i++){
		for(int j=0;j<bucketSize[i];j++) 
			aux[id++]=bucket[i][j];
		bucketSize[i]=0;	
	}
	
	for(int i=0;i<n;i++) bucket[i/blockSize][i%blockSize]=aux[i], bucketSize[i/blockSize]++;
	for(int i=0;i<=(n-1)/blockSize;i++) calcRes(i);
	
	//cout << "after recalculation:\n";
	//for(int a=0;a<=(n-1)/blockSize;a++){
		//cout << "bucket " << a << ":\n";
		//for(int j=0;j<bucketSize[a];j++) cout << bucket[a][j] << " \n"[j==bucketSize[a]-1];
	//}
	//cout << "\n";
}

int getAns(){
	int ans, ini;
	if(bucketSize[0]) ans=qtd[0][0], ini=fim[0][0];
	else ans=qtd[1][0], ini=fim[1][0];
	for(int i=1;i<=(n-1)/blockSize;i++){
		if(!bucketSize[i] || bucket[i][bucketSize[i]-1]<=ini) continue;
		int l=0, r=bucketSize[i]-1, best=-1;
		while(l<=r){
			int mid=(l+r)>>1;
			if(bucket[i][mid]>ini){
				best=mid;
				r=mid-1;
			}
			else l=mid+1;
		}
		
		//cout << "fim = " << fim[i][0] << "\n";
		ans+=qtd[i][best];
		ini=fim[i][best];
	}
	
	return ans;
}
		

void init(int N, int L, int X[])
{
	n=N; cnt=0; lim=L;
	for(int i=0;i<N;i++) arr[i]=X[i];
	for(int i=0;i<N;i++) bucket[i/blockSize][i%blockSize]=arr[i], bucketSize[i/blockSize]++;
	for(int i=0;i<=(N-1)/blockSize;i++) calcRes(i);
}

int update(int i, int y)
{
	cnt++;
	if(cnt==blockSize-20){
		cnt=0;
		recalculate();
	}
	
	removeFromBucket(arr[i]);
	addToBucket(y);
	arr[i]=y;
	
	//cout << "after update:\n";
	//for(int a=0;a<=(n-1)/blockSize;a++){
		//cout << "bucket " << a << ":\n";
		//for(int j=0;j<bucketSize[a];j++) cout << bucket[a][j] << " \n"[j==bucketSize[a]-1];
	//}
	//cout << "\n";
	
	return getAns();
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 3 ms 12632 KB Output is correct
4 Correct 2 ms 12632 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12632 KB Output is correct
7 Correct 159 ms 12632 KB Output is correct
8 Correct 172 ms 12796 KB Output is correct
9 Correct 201 ms 12904 KB Output is correct
10 Correct 217 ms 14236 KB Output is correct
11 Correct 196 ms 14168 KB Output is correct
12 Correct 354 ms 14420 KB Output is correct
13 Correct 231 ms 13912 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 3 ms 12632 KB Output is correct
4 Correct 2 ms 12632 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12632 KB Output is correct
7 Correct 159 ms 12632 KB Output is correct
8 Correct 172 ms 12796 KB Output is correct
9 Correct 201 ms 12904 KB Output is correct
10 Correct 217 ms 14236 KB Output is correct
11 Correct 196 ms 14168 KB Output is correct
12 Correct 354 ms 14420 KB Output is correct
13 Correct 231 ms 13912 KB Output is correct
14 Correct 193 ms 14416 KB Output is correct
15 Correct 272 ms 14160 KB Output is correct
16 Correct 632 ms 14712 KB Output is correct
17 Correct 638 ms 14876 KB Output is correct
18 Correct 695 ms 14868 KB Output is correct
19 Correct 351 ms 15064 KB Output is correct
20 Correct 645 ms 14936 KB Output is correct
21 Correct 595 ms 14928 KB Output is correct
22 Correct 369 ms 14672 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 3 ms 12632 KB Output is correct
4 Correct 2 ms 12632 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12632 KB Output is correct
7 Correct 159 ms 12632 KB Output is correct
8 Correct 172 ms 12796 KB Output is correct
9 Correct 201 ms 12904 KB Output is correct
10 Correct 217 ms 14236 KB Output is correct
11 Correct 196 ms 14168 KB Output is correct
12 Correct 354 ms 14420 KB Output is correct
13 Correct 231 ms 13912 KB Output is correct
14 Correct 193 ms 14416 KB Output is correct
15 Correct 272 ms 14160 KB Output is correct
16 Correct 632 ms 14712 KB Output is correct
17 Correct 638 ms 14876 KB Output is correct
18 Correct 695 ms 14868 KB Output is correct
19 Correct 351 ms 15064 KB Output is correct
20 Correct 645 ms 14936 KB Output is correct
21 Correct 595 ms 14928 KB Output is correct
22 Correct 369 ms 14672 KB Output is correct
23 Correct 1788 ms 17924 KB Output is correct
24 Correct 2009 ms 18004 KB Output is correct
25 Correct 1177 ms 17936 KB Output is correct
26 Correct 1556 ms 17936 KB Output is correct
27 Correct 1574 ms 17832 KB Output is correct
28 Correct 779 ms 15692 KB Output is correct
29 Correct 752 ms 15688 KB Output is correct
30 Correct 779 ms 15684 KB Output is correct
31 Correct 746 ms 15668 KB Output is correct
32 Correct 1095 ms 17492 KB Output is correct
33 Correct 994 ms 16724 KB Output is correct
34 Correct 1360 ms 17748 KB Output is correct
35 Correct 932 ms 17868 KB Output is correct
36 Correct 613 ms 17492 KB Output is correct
37 Correct 1705 ms 18004 KB Output is correct
38 Correct 1410 ms 16716 KB Output is correct
39 Correct 1282 ms 17748 KB Output is correct
40 Correct 1387 ms 16468 KB Output is correct
41 Correct 2230 ms 17360 KB Output is correct
42 Correct 2343 ms 17588 KB Output is correct