oj.uz

Submission #1022798

# Submission time Handle Problem Language Result Execution time Memory
1022798 2024-07-14T05:21:59 Z socpite Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 27560 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;
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 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 420 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 539 ms 3376 KB Output is correct
8 Correct 625 ms 4188 KB Output is correct
9 Correct 2167 ms 9832 KB Output is correct
10 Correct 1180 ms 14432 KB Output is correct
11 Correct 955 ms 10688 KB Output is correct
12 Correct 4103 ms 10748 KB Output is correct
13 Correct 3576 ms 14388 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 420 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 539 ms 3376 KB Output is correct
8 Correct 625 ms 4188 KB Output is correct
9 Correct 2167 ms 9832 KB Output is correct
10 Correct 1180 ms 14432 KB Output is correct
11 Correct 955 ms 10688 KB Output is correct
12 Correct 4103 ms 10748 KB Output is correct
13 Correct 3576 ms 14388 KB Output is correct
14 Correct 1723 ms 7508 KB Output is correct
15 Correct 923 ms 6932 KB Output is correct
16 Correct 6160 ms 11648 KB Output is correct
17 Correct 7879 ms 15068 KB Output is correct
18 Correct 7542 ms 15252 KB Output is correct
19 Correct 2829 ms 15464 KB Output is correct
20 Correct 7874 ms 15092 KB Output is correct
21 Correct 7468 ms 13812 KB Output is correct
22 Correct 4895 ms 16996 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 420 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 539 ms 3376 KB Output is correct
8 Correct 625 ms 4188 KB Output is correct
9 Correct 2167 ms 9832 KB Output is correct
10 Correct 1180 ms 14432 KB Output is correct
11 Correct 955 ms 10688 KB Output is correct
12 Correct 4103 ms 10748 KB Output is correct
13 Correct 3576 ms 14388 KB Output is correct
14 Correct 1723 ms 7508 KB Output is correct
15 Correct 923 ms 6932 KB Output is correct
16 Correct 6160 ms 11648 KB Output is correct
17 Correct 7879 ms 15068 KB Output is correct
18 Correct 7542 ms 15252 KB Output is correct
19 Correct 2829 ms 15464 KB Output is correct
20 Correct 7874 ms 15092 KB Output is correct
21 Correct 7468 ms 13812 KB Output is correct
22 Correct 4895 ms 16996 KB Output is correct
23 Execution timed out 9048 ms 27560 KB Time limit exceeded
24 Halted 0 ms 0 KB -