답안 #1022794

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1022794	2024-07-14T05:20:38 Z	socpite	코끼리 (Dancing Elephants) (IOI11_elephants)	C++17	50 / 100	9000 ms	15064 KB

elephants

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-