답안 #423233

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
423233	2021-06-10T20:22:01 Z	arayi	코끼리 (Dancing Elephants) (IOI11_elephants)	C++17	26 / 100	9000 ms	14676 KB

elephants

#include "elephants.h"
#include <map>
#include <unordered_map>
#include <set>
#include <iostream>
using namespace std;

const int N = 2e5 + 30;
const int T = 80;
int n, l, fr, sc, ii;
int x[N];
unordered_map <int, int> mp, cl;
int nax[N], haj[N], a[N], b[N], x1[N];
set <int> fp;

void go(int x)
{
	int sm = 1, s = 0;
	int nx = x, v = x;
	while (s < T)
	{
		s++;
		if (x1[v] > x1[nx] + l) sm++, nx = v;
		if (x1[v] == sc) break;
		v = haj[v];
	}
	a[x] = sm;
	b[x] = x1[nx] + l;
}
void add(int x)
{
	mp[x] = ++ii; x1[ii] = x;
	auto i1 = fp.lower_bound(x);
	if (i1 != fp.end()) haj[ii] = mp[*i1], nax[mp[*i1]] = ii;
	if (i1 != fp.begin()) nax[ii] = mp[*(--i1)], haj[mp[*i1]] = ii;
	fp.insert(x);
	i1 = fp.end();
	fr = *fp.begin(), sc = *(--i1);
	int v = ii;
	for (int i = 0; i <= T + 2; i++)
	{
		go(v);
		if (x1[v] == fr) break;
		v = nax[v];
	}
}
void rmv(int x)
{
	int ii = mp[x];
	mp[x] = 0;
	if (x != sc && x != fr) haj[nax[ii]] = haj[ii], nax[haj[ii]] = nax[ii];
	fp.erase(x);
	auto i1 = fp.end();
	fr = *fp.begin(), sc = *(--i1);
	int v = ii;
	for (int i = 0; i <= T + 2; i++)
	{
		if (x1[v] == fr) break;
		v = nax[v];
		go(v);
	}
}
int ans()
{
	int v = mp[fr], ret = 0;
	while (x1[v] <= sc)
	{
		ret += a[v];
		if (b[v] >= sc) break;
		v = mp[*fp.lower_bound(b[v] + 1)];
	}
	return ret;
}
void init(int N, int L, int X[])
{
	n = N; l = L;
	for (int i = 0; i < n; i++)
	{
		x[i] = X[i];
		if (cl[x[i]] == 0) add(x[i]);
		cl[x[i]]++;
	}
}

int update(int i, int y)
{
	cl[x[i]]--;
	if (cl[x[i]] == 0) rmv(x[i]);
	x[i] = y;
	cl[y]++;
	if (cl[y] == 1) add(y);
	return ans();
}

Subtask #1

10.0 / 10.0

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

Subtask #2

16.0 / 16.0

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

Subtask #3

0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	3 ms	332 KB	Output is correct
5	Correct	3 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	2920 ms	7764 KB	Output is correct
8	Correct	3583 ms	8648 KB	Output is correct
9	Correct	8670 ms	11288 KB	Output is correct
10	Correct	8200 ms	14520 KB	Output is correct
11	Correct	5256 ms	14676 KB	Output is correct
12	Execution timed out	9044 ms	14136 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-

Subtask #4

0 / 47.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	3 ms	332 KB	Output is correct
5	Correct	3 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	2920 ms	7764 KB	Output is correct
8	Correct	3583 ms	8648 KB	Output is correct
9	Correct	8670 ms	11288 KB	Output is correct
10	Correct	8200 ms	14520 KB	Output is correct
11	Correct	5256 ms	14676 KB	Output is correct
12	Execution timed out	9044 ms	14136 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-

Subtask #5

0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	3 ms	332 KB	Output is correct
5	Correct	3 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	2920 ms	7764 KB	Output is correct
8	Correct	3583 ms	8648 KB	Output is correct
9	Correct	8670 ms	11288 KB	Output is correct
10	Correct	8200 ms	14520 KB	Output is correct
11	Correct	5256 ms	14676 KB	Output is correct
12	Execution timed out	9044 ms	14136 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-