oj.uz

Submission #529388

# Submission time Handle Problem Language Result Execution time Memory
529388 2022-02-22T23:33:21 Z flappybird Dancing Elephants (IOI11_elephants) C++14
100 / 100
 8087 ms 35920 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 INF 1000000010
#define B 300

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

inline bool cmpp(const pair<int, pi>& p1, const pair<int, pi>& p2) {
	return p1.first < p2.first;
}

//refresh bukkit
void refb(int b) {
	if (bukkit[b].empty()) return;
	while (bukkit[b].size() && bukkit[b].back().first == INF) bukkit[b].pop_back();
	int i;
	int ub = bukkit[b].size();
	for (i = bukkit[b].size() - 1; i >= 0; i--) {
		int x = bukkit[b][i].first;
		int e = x + L;
		while (ub && bukkit[b][ub - 1].first > e) ub--;
		if (ub == bukkit[b].size()) bukkit[b][i].second = pi(1, e);
		else bukkit[b][i].second = pi(bukkit[b][ub].second.first + 1, bukkit[b][ub].second.second);
	}
}

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].push_back(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 = lower_bound(bukkit[i].begin(), bukkit[i].end(), make_pair(en + 1, pi(0, 0)), cmpp) - bukkit[i].begin();
		if (ub == bukkit[i].size()) continue;
		cnt += bukkit[i][ub].second.first;
		en = bukkit[i][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;
		int it = lower_bound(bukkit[ind].begin(), bukkit[ind].end(), make_pair(x, pi(0, 0)), cmpp) - bukkit[ind].begin();
		bukkit[ind].erase(bukkit[ind].begin() + 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;
		int nind;
		nind = lower_bound(bukkit[ind].begin(), bukkit[ind].end(), make_pair(y, pi(0, 0))) - bukkit[ind].begin();
		bukkit[ind].insert(bukkit[ind].begin() + nind, make_pair(y, pi(0, 0)));
		allv.insert(y);
		refb(ind);
	}
	ncnt[y]++;
	return calc();
}

Compilation message

elephants.cpp: In function 'void refb(int)':
elephants.cpp:38:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   if (ub == bukkit[b].size()) bukkit[b][i].second = pi(1, e);
      |       ~~~^~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'int calc()':
elephants.cpp:60:10: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   if (ub == bukkit[i].size()) continue;
      |       ~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3788 KB Output is correct
2 Correct 2 ms 3788 KB Output is correct
3 Correct 3 ms 3788 KB Output is correct
4 Correct 2 ms 3788 KB Output is correct
5 Correct 2 ms 3788 KB Output is correct
6 Correct 2 ms 3788 KB Output is correct
7 Correct 342 ms 8088 KB Output is correct
8 Correct 328 ms 8772 KB Output is correct
9 Correct 506 ms 11404 KB Output is correct
10 Correct 468 ms 12880 KB Output is correct
11 Correct 459 ms 12808 KB Output is correct
12 Correct 914 ms 12800 KB Output is correct
13 Correct 486 ms 12764 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3788 KB Output is correct
2 Correct 2 ms 3788 KB Output is correct
3 Correct 3 ms 3788 KB Output is correct
4 Correct 2 ms 3788 KB Output is correct
5 Correct 2 ms 3788 KB Output is correct
6 Correct 2 ms 3788 KB Output is correct
7 Correct 342 ms 8088 KB Output is correct
8 Correct 328 ms 8772 KB Output is correct
9 Correct 506 ms 11404 KB Output is correct
10 Correct 468 ms 12880 KB Output is correct
11 Correct 459 ms 12808 KB Output is correct
12 Correct 914 ms 12800 KB Output is correct
13 Correct 486 ms 12764 KB Output is correct
14 Correct 242 ms 8392 KB Output is correct
15 Correct 594 ms 10564 KB Output is correct
16 Correct 1235 ms 13352 KB Output is correct
17 Correct 1711 ms 15904 KB Output is correct
18 Correct 1730 ms 16228 KB Output is correct
19 Correct 875 ms 16424 KB Output is correct
20 Correct 1843 ms 16364 KB Output is correct
21 Correct 1706 ms 16452 KB Output is correct
22 Correct 983 ms 16360 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3788 KB Output is correct
2 Correct 2 ms 3788 KB Output is correct
3 Correct 3 ms 3788 KB Output is correct
4 Correct 2 ms 3788 KB Output is correct
5 Correct 2 ms 3788 KB Output is correct
6 Correct 2 ms 3788 KB Output is correct
7 Correct 342 ms 8088 KB Output is correct
8 Correct 328 ms 8772 KB Output is correct
9 Correct 506 ms 11404 KB Output is correct
10 Correct 468 ms 12880 KB Output is correct
11 Correct 459 ms 12808 KB Output is correct
12 Correct 914 ms 12800 KB Output is correct
13 Correct 486 ms 12764 KB Output is correct
14 Correct 242 ms 8392 KB Output is correct
15 Correct 594 ms 10564 KB Output is correct
16 Correct 1235 ms 13352 KB Output is correct
17 Correct 1711 ms 15904 KB Output is correct
18 Correct 1730 ms 16228 KB Output is correct
19 Correct 875 ms 16424 KB Output is correct
20 Correct 1843 ms 16364 KB Output is correct
21 Correct 1706 ms 16452 KB Output is correct
22 Correct 983 ms 16360 KB Output is correct
23 Correct 6551 ms 28300 KB Output is correct
24 Correct 6721 ms 31812 KB Output is correct
25 Correct 5139 ms 31664 KB Output is correct
26 Correct 4496 ms 35920 KB Output is correct
27 Correct 4969 ms 35648 KB Output is correct
28 Correct 1269 ms 13568 KB Output is correct
29 Correct 1224 ms 12988 KB Output is correct
30 Correct 1316 ms 13652 KB Output is correct
31 Correct 1221 ms 13028 KB Output is correct
32 Correct 4051 ms 35380 KB Output is correct
33 Correct 1949 ms 30100 KB Output is correct
34 Correct 3971 ms 35556 KB Output is correct
35 Correct 1856 ms 28912 KB Output is correct
36 Correct 61 ms 11132 KB Output is correct
37 Correct 3329 ms 28736 KB Output is correct
38 Correct 3984 ms 34524 KB Output is correct
39 Correct 3486 ms 35636 KB Output is correct
40 Correct 3934 ms 34544 KB Output is correct
41 Correct 7582 ms 34248 KB Output is correct
42 Correct 8087 ms 34660 KB Output is correct