oj.uz

Submission #529387

# Submission time Handle Problem Language Result Execution time Memory
529387 2022-02-22T23:22:31 Z flappybird Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 27008 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 400

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;
	sort(bukkit[b].begin(), bukkit[b].end());
	while (bukkit[b].size() && bukkit[b].back().first == INF) bukkit[b].pop_back();
	int i;
	for (i = bukkit[b].size() - 1; i >= 0; i--) {
		int x = bukkit[b][i].first;
		int e = x + L;
		int ub = lower_bound(bukkit[b].begin(), bukkit[b].end(), make_pair(e + 1, pi(0, 0)), cmpp) - bukkit[b].begin();
		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][it].first = INF;
		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].push_back(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 2 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 2 ms 3788 KB Output is correct
4 Correct 3 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 2 ms 3788 KB Output is correct
4 Correct 3 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 1690 ms 8004 KB Output is correct
8 Correct 1711 ms 8692 KB Output is correct
9 Correct 1947 ms 11172 KB Output is correct
10 Correct 1737 ms 12688 KB Output is correct
11 Correct 1596 ms 12672 KB Output is correct
12 Correct 2610 ms 12580 KB Output is correct
13 Correct 1725 ms 12532 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 2 ms 3788 KB Output is correct
4 Correct 3 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 1690 ms 8004 KB Output is correct
8 Correct 1711 ms 8692 KB Output is correct
9 Correct 1947 ms 11172 KB Output is correct
10 Correct 1737 ms 12688 KB Output is correct
11 Correct 1596 ms 12672 KB Output is correct
12 Correct 2610 ms 12580 KB Output is correct
13 Correct 1725 ms 12532 KB Output is correct
14 Correct 1161 ms 8276 KB Output is correct
15 Correct 2557 ms 10432 KB Output is correct
16 Correct 3391 ms 13052 KB Output is correct
17 Correct 3994 ms 15556 KB Output is correct
18 Correct 4006 ms 15784 KB Output is correct
19 Correct 4728 ms 16188 KB Output is correct
20 Correct 4265 ms 16104 KB Output is correct
21 Correct 4172 ms 16116 KB Output is correct
22 Correct 2522 ms 16208 KB Output is correct

Subtask #5
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 2 ms 3788 KB Output is correct
4 Correct 3 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 1690 ms 8004 KB Output is correct
8 Correct 1711 ms 8692 KB Output is correct
9 Correct 1947 ms 11172 KB Output is correct
10 Correct 1737 ms 12688 KB Output is correct
11 Correct 1596 ms 12672 KB Output is correct
12 Correct 2610 ms 12580 KB Output is correct
13 Correct 1725 ms 12532 KB Output is correct
14 Correct 1161 ms 8276 KB Output is correct
15 Correct 2557 ms 10432 KB Output is correct
16 Correct 3391 ms 13052 KB Output is correct
17 Correct 3994 ms 15556 KB Output is correct
18 Correct 4006 ms 15784 KB Output is correct
19 Correct 4728 ms 16188 KB Output is correct
20 Correct 4265 ms 16104 KB Output is correct
21 Correct 4172 ms 16116 KB Output is correct
22 Correct 2522 ms 16208 KB Output is correct
23 Execution timed out 9087 ms 27008 KB Time limit exceeded
24 Halted 0 ms 0 KB -