oj.uz

Submission #529382

# Submission time Handle Problem Language Result Execution time Memory
529382 2022-02-22T22:59:02 Z flappybird Dancing Elephants (IOI11_elephants) C++17
50 / 100
 9000 ms 21472 KB 
#include "elephants.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
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 5 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7368 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7368 KB Output is correct
4 Correct 6 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 5 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7368 KB Output is correct
4 Correct 6 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 2812 ms 12300 KB Output is correct
8 Correct 3157 ms 13052 KB Output is correct
9 Correct 5557 ms 17056 KB Output is correct
10 Correct 5352 ms 18632 KB Output is correct
11 Correct 4951 ms 18528 KB Output is correct
12 Correct 6960 ms 18500 KB Output is correct
13 Correct 5027 ms 18540 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7368 KB Output is correct
4 Correct 6 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 2812 ms 12300 KB Output is correct
8 Correct 3157 ms 13052 KB Output is correct
9 Correct 5557 ms 17056 KB Output is correct
10 Correct 5352 ms 18632 KB Output is correct
11 Correct 4951 ms 18528 KB Output is correct
12 Correct 6960 ms 18500 KB Output is correct
13 Correct 5027 ms 18540 KB Output is correct
14 Correct 2082 ms 12860 KB Output is correct
15 Correct 4934 ms 15288 KB Output is correct
16 Correct 8738 ms 18780 KB Output is correct
17 Execution timed out 9071 ms 21472 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7368 KB Output is correct
4 Correct 6 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 2812 ms 12300 KB Output is correct
8 Correct 3157 ms 13052 KB Output is correct
9 Correct 5557 ms 17056 KB Output is correct
10 Correct 5352 ms 18632 KB Output is correct
11 Correct 4951 ms 18528 KB Output is correct
12 Correct 6960 ms 18500 KB Output is correct
13 Correct 5027 ms 18540 KB Output is correct
14 Correct 2082 ms 12860 KB Output is correct
15 Correct 4934 ms 15288 KB Output is correct
16 Correct 8738 ms 18780 KB Output is correct
17 Execution timed out 9071 ms 21472 KB Time limit exceeded
18 Halted 0 ms 0 KB -