oj.uz

Submission #363536

# Submission time Handle Problem Language Result Execution time Memory
363536 2021-02-06T13:21:29 Z soroush Dancing Elephants (IOI11_elephants) C++14
26 / 100
 466 ms 4204 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int maxn = 3e5 + 100;
const int sq = 400;
 
int n , l , SZ , cnt , ucnt;
int x[maxn];
int a[maxn];
 
struct comp{
	int a[sq * 2] , cnt[sq * 2] , lst[sq * 2] , sz;
	void init(){
		int k = sz;
		for(int i = sz ; i ; i --){
			while(k > i and a[k - 1] - a[i] > l)k --;
			if(a[sz] - a[i] <= l) cnt[i] = 1 , lst[i] = a[i] + l;
			else cnt[i] = cnt[k] + 1 , lst[i] = lst[k];
		}
	}
}comps[sq];
 
void init(int N , int L , int X[]){
	n = N , l = L;
	SZ = sq-10 , cnt = 1;
	for(int i = 0 ; i < n ; i ++){
		x[i] = X[i];
		if(comps[cnt].sz == SZ)cnt++;
		comps[cnt].a[++comps[cnt].sz] = x[i];
	}
	for(int i = 1 ; i <= cnt ; i ++)comps[i].init();
}
 
 
void add(int pos){
	int j , x;
	for(j = 1 ; j < cnt ; j ++)	if(comps[j].a[comps[j].sz] > pos)break;
	for(x = 1 ; x <= comps[j].sz ; x++)if(comps[j].a[x] > pos)break;
	for(int i = comps[j].sz ; i >= x ; i --) comps[j].a[i+1] = comps[j].a[i];
	comps[j].a[x] = pos;
	comps[j].sz++;
	comps[j].init();
}
 
void build(){
	int n = -1;
	for(int i = 1 ; i <= cnt ; i ++){
		for(int j = 1 ; j <= comps[i].sz ; j ++)
			x[++n] = comps[i].a[j];
		comps[i].sz = 0;
	}
	cnt = 1;
	for(int i = 0 ; i <= n ; i ++){
		if(comps[cnt].sz == SZ)cnt++;
		comps[cnt].a[++comps[cnt].sz] = x[i];
	}
	for(int i = 1 ; i <= cnt ; i ++)comps[i].init();
	ucnt = 0;
}
 
int rm(int pos){
	int j , i;
	for(j = 1 ; j < cnt ; j ++)	if(comps[j].a[1] <= pos and comps[j + 1].a[1] > pos)break;
	for(i = 1 ; i <= comps[j].sz ; i ++)if(comps[j].a[i] == pos){
		for(; i < comps[j].sz ; i ++) comps[j].a[i] = comps[j].a[i + 1];
		comps[j].sz --;
		break;
	}
	comps[j].init();
	return(comps[j].sz);
}
 
int get(){
	int ans = comps[1].cnt[1] , lst = comps[1].lst[1] , t;
	for(int i = 2 ; i <= cnt ; i ++){
		if(comps[i].a[comps[i].sz] <= lst)continue;
		int l = 1 , r = comps[i].sz;
		while(l <= r){
			int mid = (l + r) / 2;
			if(comps[i].a[mid] > lst)r = mid - 1 , t = mid;
			else l = mid + 1;
		}
		ans += comps[i].cnt[t];
		lst = comps[i].lst[t];
	}
	return(ans);
}
 
int update(int p , int v){
	if(++ucnt == SZ)build();
	if(!rm(x[p]))build();
	add(x[p] = v);
	return(get());
}

Compilation message

elephants.cpp: In function 'int get()':
elephants.cpp:87:7: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |   lst = comps[i].lst[t];
      |   ~~~~^~~~~~~~~~~~~~~~~

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
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 449 ms 1424 KB Output is correct
8 Correct 466 ms 2600 KB Output is correct
9 Correct 394 ms 4204 KB Output is correct
10 Incorrect 168 ms 3948 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
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 449 ms 1424 KB Output is correct
8 Correct 466 ms 2600 KB Output is correct
9 Correct 394 ms 4204 KB Output is correct
10 Incorrect 168 ms 3948 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
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 449 ms 1424 KB Output is correct
8 Correct 466 ms 2600 KB Output is correct
9 Correct 394 ms 4204 KB Output is correct
10 Incorrect 168 ms 3948 KB Output isn't correct
11 Halted 0 ms 0 KB -