oj.uz

Submission #1022802

# Submission time Handle Problem Language Result Execution time Memory
1022802 2024-07-14T05:23:08 Z socpite Dancing Elephants (IOI11_elephants) C++14
50 / 100
 9000 ms 13152 KB 
#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
 
const int blsz = 200;
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 2 ms 604 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 2 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 457 ms 4264 KB Output is correct
8 Correct 547 ms 4956 KB Output is correct
9 Correct 1570 ms 11368 KB Output is correct
10 Correct 439 ms 12728 KB Output is correct
11 Correct 961 ms 10896 KB Output is correct
12 Correct 5069 ms 10852 KB Output is correct
13 Correct 1442 ms 11824 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 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 2 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 457 ms 4264 KB Output is correct
8 Correct 547 ms 4956 KB Output is correct
9 Correct 1570 ms 11368 KB Output is correct
10 Correct 439 ms 12728 KB Output is correct
11 Correct 961 ms 10896 KB Output is correct
12 Correct 5069 ms 10852 KB Output is correct
13 Correct 1442 ms 11824 KB Output is correct
14 Correct 1171 ms 6228 KB Output is correct
15 Correct 982 ms 5292 KB Output is correct
16 Correct 6175 ms 10092 KB Output is correct
17 Execution timed out 9091 ms 13152 KB Time limit exceeded
18 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 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 2 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 457 ms 4264 KB Output is correct
8 Correct 547 ms 4956 KB Output is correct
9 Correct 1570 ms 11368 KB Output is correct
10 Correct 439 ms 12728 KB Output is correct
11 Correct 961 ms 10896 KB Output is correct
12 Correct 5069 ms 10852 KB Output is correct
13 Correct 1442 ms 11824 KB Output is correct
14 Correct 1171 ms 6228 KB Output is correct
15 Correct 982 ms 5292 KB Output is correct
16 Correct 6175 ms 10092 KB Output is correct
17 Execution timed out 9091 ms 13152 KB Time limit exceeded
18 Halted 0 ms 0 KB -