oj.uz

Submission #1022796

# Submission time Handle Problem Language Result Execution time Memory
1022796 2024-07-14T05:21:17 Z socpite Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 31688 KB 
#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;

const int blsz = 300;
const int maxn = 2e5+5;
const int INF = 2e9+5;

int sp[18][maxn];
multiset<int> current;
unordered_map<int, int> vmap;
multiset<int> changed;

int A[maxn];
int dval[maxn];

int n, l;

void build_sp(){

	changed = {INF};
	vmap.clear();
	int crr = 0;
	for(auto v: current)if(!crr || dval[crr-1] != v){
		vmap[v] = crr;
		dval[crr++] = v;
	}
	for(int i = 0; i < crr-1; i++){
		sp[0][i] = upper_bound(dval, dval + crr, dval[i] + l) - dval;
	}
	sp[0][crr-1] = crr-1;
	for(int i = 1; i < 18; i++){
		for(int j = 0; j < crr; j++)sp[i][j] = sp[i-1][sp[i-1][j]];
	}
}

void init(int N, int L, int X[])
{
  	n = N;
	l = L;
	current.insert(INF);
	for(int i = 0; i < N; i++){
		A[i] = X[i];
		current.insert(A[i]);
	}
	build_sp();
}

int update(int i, int y)
{
	current.erase(current.find(A[i]));
	changed.insert(A[i]);
	A[i] = y;
	current.insert(A[i]);
	changed.insert(A[i]);

	int realcnt = 0, ans = 0;
	int pos = *current.begin();
	while(pos != INF){
		realcnt++;
		if(changed.find(pos) != changed.end()){
			if(current.find(pos) == current.end())pos = *current.upper_bound(pos);
			else {
				ans++;
				pos = *current.upper_bound(pos + l);
			}
		}
		else {
			int nxt_change = *changed.upper_bound(pos);
			int id = vmap[pos];
			for(int i = 17; i >= 0; i--){
				if(dval[sp[i][id]] < nxt_change){
					id = sp[i][id];
					ans += (1<<i);
				}
			}
			pos = *current.upper_bound(dval[id] + l);
			ans++;
		}
	}
	if(realcnt >= blsz)build_sp();
	return ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 408 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 452 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 408 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 452 KB Output is correct
7 Correct 499 ms 4268 KB Output is correct
8 Correct 537 ms 4956 KB Output is correct
9 Correct 1982 ms 11364 KB Output is correct
10 Correct 811 ms 13960 KB Output is correct
11 Correct 994 ms 11176 KB Output is correct
12 Correct 4580 ms 11284 KB Output is correct
13 Correct 2486 ms 13416 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 408 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 452 KB Output is correct
7 Correct 499 ms 4268 KB Output is correct
8 Correct 537 ms 4956 KB Output is correct
9 Correct 1982 ms 11364 KB Output is correct
10 Correct 811 ms 13960 KB Output is correct
11 Correct 994 ms 11176 KB Output is correct
12 Correct 4580 ms 11284 KB Output is correct
13 Correct 2486 ms 13416 KB Output is correct
14 Correct 1375 ms 6480 KB Output is correct
15 Correct 896 ms 5508 KB Output is correct
16 Correct 5343 ms 10092 KB Output is correct
17 Correct 7377 ms 13288 KB Output is correct
18 Correct 7640 ms 13300 KB Output is correct
19 Correct 2106 ms 14688 KB Output is correct
20 Correct 8663 ms 13284 KB Output is correct
21 Correct 8298 ms 14572 KB Output is correct
22 Correct 3696 ms 17560 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 408 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 452 KB Output is correct
7 Correct 499 ms 4268 KB Output is correct
8 Correct 537 ms 4956 KB Output is correct
9 Correct 1982 ms 11364 KB Output is correct
10 Correct 811 ms 13960 KB Output is correct
11 Correct 994 ms 11176 KB Output is correct
12 Correct 4580 ms 11284 KB Output is correct
13 Correct 2486 ms 13416 KB Output is correct
14 Correct 1375 ms 6480 KB Output is correct
15 Correct 896 ms 5508 KB Output is correct
16 Correct 5343 ms 10092 KB Output is correct
17 Correct 7377 ms 13288 KB Output is correct
18 Correct 7640 ms 13300 KB Output is correct
19 Correct 2106 ms 14688 KB Output is correct
20 Correct 8663 ms 13284 KB Output is correct
21 Correct 8298 ms 14572 KB Output is correct
22 Correct 3696 ms 17560 KB Output is correct
23 Execution timed out 9041 ms 31688 KB Time limit exceeded
24 Halted 0 ms 0 KB -