oj.uz

답안 #1022808

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1022808 2024-07-14T05:24:38 Z socpite 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
97 / 100
 9000 ms 32092 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 582 ms 4288 KB Output is correct
8 Correct 660 ms 5192 KB Output is correct
9 Correct 2484 ms 11416 KB Output is correct
10 Correct 1094 ms 14920 KB Output is correct
11 Correct 939 ms 11188 KB Output is correct
12 Correct 4430 ms 11288 KB Output is correct
13 Correct 3590 ms 14452 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 582 ms 4288 KB Output is correct
8 Correct 660 ms 5192 KB Output is correct
9 Correct 2484 ms 11416 KB Output is correct
10 Correct 1094 ms 14920 KB Output is correct
11 Correct 939 ms 11188 KB Output is correct
12 Correct 4430 ms 11288 KB Output is correct
13 Correct 3590 ms 14452 KB Output is correct
14 Correct 1524 ms 6148 KB Output is correct
15 Correct 997 ms 6328 KB Output is correct
16 Correct 5981 ms 11360 KB Output is correct
17 Correct 7898 ms 13300 KB Output is correct
18 Correct 7433 ms 13300 KB Output is correct
19 Correct 2606 ms 14944 KB Output is correct
20 Correct 7530 ms 14576 KB Output is correct
21 Correct 7853 ms 15296 KB Output is correct
22 Correct 4947 ms 18524 KB Output is correct

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 582 ms 4288 KB Output is correct
8 Correct 660 ms 5192 KB Output is correct
9 Correct 2484 ms 11416 KB Output is correct
10 Correct 1094 ms 14920 KB Output is correct
11 Correct 939 ms 11188 KB Output is correct
12 Correct 4430 ms 11288 KB Output is correct
13 Correct 3590 ms 14452 KB Output is correct
14 Correct 1524 ms 6148 KB Output is correct
15 Correct 997 ms 6328 KB Output is correct
16 Correct 5981 ms 11360 KB Output is correct
17 Correct 7898 ms 13300 KB Output is correct
18 Correct 7433 ms 13300 KB Output is correct
19 Correct 2606 ms 14944 KB Output is correct
20 Correct 7530 ms 14576 KB Output is correct
21 Correct 7853 ms 15296 KB Output is correct
22 Correct 4947 ms 18524 KB Output is correct
23 Execution timed out 9056 ms 32092 KB Time limit exceeded
24 Halted 0 ms 0 KB -