oj.uz

Submission #529379

# Submission time Handle Problem Language Result Execution time Memory
529379 2022-02-22T22:53:57 Z flappybird Dancing Elephants (IOI11_elephants) C++17
50 / 100
 9000 ms 20580 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
#define MAX 150010
#define B 400

int N;
int L;
int arr[MAX];
int cnt;
map<int, int> ncnt;
int gcnt;
set<int> allv;
set<pair<int, pi>> bukkit[MAX];

//refresh bukkit
void refb(int b) {
	if (bukkit[b].empty()) return;
	set<pair<int, pi>> s1;
	for (auto it = prev(bukkit[b].end());; it--) {
		int x = it->first;
		int e = x + L;
		auto ub = s1.lower_bound(make_pair(e + 1, pi(0, 0)));
		pair<int, pi> ins;
		ins.first = x;
		if (ub == s1.end()) ins.second = pi(1, e);
		else ins.second = pi(ub->second.first + 1, ub->second.second);
		s1.insert(ins);
		if (it == bukkit[b].begin()) break;
	}
	bukkit[b].swap(s1);
}

void ref() {
	for (int i = 0; i < gcnt; i++) bukkit[i].clear();
	gcnt = 0;
	for (auto v : allv) {
		if (bukkit[gcnt].size() == B) gcnt++;
		bukkit[gcnt].insert(make_pair(v, pi(0, 0)));
	}
	gcnt++;
	for (int i = 0; i < gcnt; i++) refb(i);
}

int calc() {
	int en = -2, i;
	int cnt = 0;
	for (i = 0; i < gcnt; i++) {
		if (bukkit[i].empty()) continue;
		auto ub = bukkit[i].lower_bound(make_pair(en + 1, pi(0, 0)));
		if (ub == bukkit[i].end()) continue;
		cnt += ub->second.first;
		en = ub->second.second;
	}
	return cnt;
}

void init(int N, int L, int X[]) {
	::N = N;
	::L = L;
	int i;
	for (i = 0; i < N; i++) arr[i] = X[i], allv.insert(arr[i]), ncnt[arr[i]]++;
	ref();
}

int update(int i, int y) {
	cnt++;
	if (cnt == B) ref(), cnt = 0;
	int x = arr[i];
	arr[i] = y;
	ncnt[x]--;
	if (ncnt[x] == 0) {
		int i, ind = 0;
		for (i = 0; i < gcnt; i++) if (bukkit[i].size() && bukkit[i].begin()->first <= x) ind = i;
		auto it = bukkit[ind].lower_bound(make_pair(x, pi(0, 0)));
		bukkit[ind].erase(it);
		allv.erase(x);
		refb(ind);
	}
	if (ncnt[y] == 0) {
		allv.insert(y);
		int i, ind = 0;
		for (i = 0; i < gcnt; i++) if (bukkit[i].size() && bukkit[i].begin()->first <= y) ind = i;
		bukkit[ind].insert(make_pair(y, pi(0, 0)));
		allv.insert(y);
		refb(ind);
	}
	ncnt[y]++;
	return calc();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 5 ms 7396 KB Output is correct
5 Correct 8 ms 7372 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 5 ms 7396 KB Output is correct
5 Correct 8 ms 7372 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 4693 ms 12108 KB Output is correct
8 Correct 4858 ms 13044 KB Output is correct
9 Correct 6310 ms 17008 KB Output is correct
10 Correct 6713 ms 18680 KB Output is correct
11 Correct 5818 ms 19840 KB Output is correct
12 Correct 7351 ms 19888 KB Output is correct
13 Correct 6452 ms 19652 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 5 ms 7396 KB Output is correct
5 Correct 8 ms 7372 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 4693 ms 12108 KB Output is correct
8 Correct 4858 ms 13044 KB Output is correct
9 Correct 6310 ms 17008 KB Output is correct
10 Correct 6713 ms 18680 KB Output is correct
11 Correct 5818 ms 19840 KB Output is correct
12 Correct 7351 ms 19888 KB Output is correct
13 Correct 6452 ms 19652 KB Output is correct
14 Correct 3092 ms 14236 KB Output is correct
15 Correct 7118 ms 16532 KB Output is correct
16 Execution timed out 9098 ms 20580 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 5 ms 7396 KB Output is correct
5 Correct 8 ms 7372 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 4693 ms 12108 KB Output is correct
8 Correct 4858 ms 13044 KB Output is correct
9 Correct 6310 ms 17008 KB Output is correct
10 Correct 6713 ms 18680 KB Output is correct
11 Correct 5818 ms 19840 KB Output is correct
12 Correct 7351 ms 19888 KB Output is correct
13 Correct 6452 ms 19652 KB Output is correct
14 Correct 3092 ms 14236 KB Output is correct
15 Correct 7118 ms 16532 KB Output is correct
16 Execution timed out 9098 ms 20580 KB Time limit exceeded
17 Halted 0 ms 0 KB -