oj.uz

Submission #529380

# Submission time Handle Problem Language Result Execution time Memory
529380 2022-02-22T22:56:11 Z flappybird Dancing Elephants (IOI11_elephants) C++17
50 / 100
 9000 ms 23460 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 200

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 7372 KB Output is correct
5 Correct 5 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 7372 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 2917 ms 12228 KB Output is correct
8 Correct 3195 ms 13004 KB Output is correct
9 Correct 5787 ms 17168 KB Output is correct
10 Correct 5500 ms 18664 KB Output is correct
11 Correct 5114 ms 18528 KB Output is correct
12 Correct 6913 ms 18496 KB Output is correct
13 Correct 5217 ms 18460 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 7372 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 2917 ms 12228 KB Output is correct
8 Correct 3195 ms 13004 KB Output is correct
9 Correct 5787 ms 17168 KB Output is correct
10 Correct 5500 ms 18664 KB Output is correct
11 Correct 5114 ms 18528 KB Output is correct
12 Correct 6913 ms 18496 KB Output is correct
13 Correct 5217 ms 18460 KB Output is correct
14 Correct 2112 ms 12832 KB Output is correct
15 Correct 5161 ms 15172 KB Output is correct
16 Correct 8709 ms 18820 KB Output is correct
17 Execution timed out 9022 ms 23460 KB Time limit exceeded
18 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 7372 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 2917 ms 12228 KB Output is correct
8 Correct 3195 ms 13004 KB Output is correct
9 Correct 5787 ms 17168 KB Output is correct
10 Correct 5500 ms 18664 KB Output is correct
11 Correct 5114 ms 18528 KB Output is correct
12 Correct 6913 ms 18496 KB Output is correct
13 Correct 5217 ms 18460 KB Output is correct
14 Correct 2112 ms 12832 KB Output is correct
15 Correct 5161 ms 15172 KB Output is correct
16 Correct 8709 ms 18820 KB Output is correct
17 Execution timed out 9022 ms 23460 KB Time limit exceeded
18 Halted 0 ms 0 KB -