oj.uz

Submission #1022794

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

const int blsz = 600;
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 0 ms 344 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 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 344 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 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 758 ms 3416 KB Output is correct
8 Correct 829 ms 4216 KB Output is correct
9 Correct 3667 ms 9912 KB Output is correct
10 Correct 2011 ms 14424 KB Output is correct
11 Correct 1343 ms 9944 KB Output is correct
12 Correct 5458 ms 9780 KB Output is correct
13 Correct 5472 ms 15064 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 758 ms 3416 KB Output is correct
8 Correct 829 ms 4216 KB Output is correct
9 Correct 3667 ms 9912 KB Output is correct
10 Correct 2011 ms 14424 KB Output is correct
11 Correct 1343 ms 9944 KB Output is correct
12 Correct 5458 ms 9780 KB Output is correct
13 Correct 5472 ms 15064 KB Output is correct
14 Correct 2858 ms 7080 KB Output is correct
15 Correct 1211 ms 6828 KB Output is correct
16 Correct 6688 ms 11892 KB Output is correct
17 Correct 8813 ms 14888 KB Output is correct
18 Execution timed out 9042 ms 14548 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 758 ms 3416 KB Output is correct
8 Correct 829 ms 4216 KB Output is correct
9 Correct 3667 ms 9912 KB Output is correct
10 Correct 2011 ms 14424 KB Output is correct
11 Correct 1343 ms 9944 KB Output is correct
12 Correct 5458 ms 9780 KB Output is correct
13 Correct 5472 ms 15064 KB Output is correct
14 Correct 2858 ms 7080 KB Output is correct
15 Correct 1211 ms 6828 KB Output is correct
16 Correct 6688 ms 11892 KB Output is correct
17 Correct 8813 ms 14888 KB Output is correct
18 Execution timed out 9042 ms 14548 KB Time limit exceeded
19 Halted 0 ms 0 KB -