oj.uz

Submission #1022805

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

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

int sp[18][maxn];
multiset<int> current;
unordered_map<int, int> vmap;
set<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 0 ms 348 KB Output is correct
3 Correct 1 ms 348 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 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 0 ms 348 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 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 554 ms 3160 KB Output is correct
8 Correct 567 ms 4188 KB Output is correct
9 Correct 2051 ms 9860 KB Output is correct
10 Correct 1068 ms 13384 KB Output is correct
11 Correct 909 ms 9824 KB Output is correct
12 Correct 4086 ms 9824 KB Output is correct
13 Correct 3365 ms 13484 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 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 554 ms 3160 KB Output is correct
8 Correct 567 ms 4188 KB Output is correct
9 Correct 2051 ms 9860 KB Output is correct
10 Correct 1068 ms 13384 KB Output is correct
11 Correct 909 ms 9824 KB Output is correct
12 Correct 4086 ms 9824 KB Output is correct
13 Correct 3365 ms 13484 KB Output is correct
14 Correct 1491 ms 5208 KB Output is correct
15 Correct 948 ms 5512 KB Output is correct
16 Correct 5621 ms 10088 KB Output is correct
17 Correct 7639 ms 14580 KB Output is correct
18 Correct 7907 ms 14568 KB Output is correct
19 Correct 2837 ms 14800 KB Output is correct
20 Correct 8849 ms 14560 KB Output is correct
21 Correct 8454 ms 14776 KB Output is correct
22 Correct 4953 ms 18132 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 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 554 ms 3160 KB Output is correct
8 Correct 567 ms 4188 KB Output is correct
9 Correct 2051 ms 9860 KB Output is correct
10 Correct 1068 ms 13384 KB Output is correct
11 Correct 909 ms 9824 KB Output is correct
12 Correct 4086 ms 9824 KB Output is correct
13 Correct 3365 ms 13484 KB Output is correct
14 Correct 1491 ms 5208 KB Output is correct
15 Correct 948 ms 5512 KB Output is correct
16 Correct 5621 ms 10088 KB Output is correct
17 Correct 7639 ms 14580 KB Output is correct
18 Correct 7907 ms 14568 KB Output is correct
19 Correct 2837 ms 14800 KB Output is correct
20 Correct 8849 ms 14560 KB Output is correct
21 Correct 8454 ms 14776 KB Output is correct
22 Correct 4953 ms 18132 KB Output is correct
23 Execution timed out 9072 ms 30972 KB Time limit exceeded
24 Halted 0 ms 0 KB -