oj.uz

Submission #529384

# Submission time Handle Problem Language Result Execution time Memory
529384 2022-02-22T23:09:34 Z flappybird Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 31580 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 200

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

//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))) - 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))) - 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))) - 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:34: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]
   34 |   if (ub == bukkit[b].size()) bukkit[b][i].second = pi(1, e);
      |       ~~~^~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'int calc()':
elephants.cpp:56: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]
   56 |   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 3 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 3 ms 3788 KB Output is correct
6 Correct 2 ms 3788 KB Output is correct
7 Correct 1196 ms 7944 KB Output is correct
8 Correct 1227 ms 8628 KB Output is correct
9 Correct 1793 ms 11124 KB Output is correct
10 Correct 1693 ms 12616 KB Output is correct
11 Correct 1548 ms 12616 KB Output is correct
12 Correct 2354 ms 12512 KB Output is correct
13 Correct 1763 ms 12636 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 3 ms 3788 KB Output is correct
6 Correct 2 ms 3788 KB Output is correct
7 Correct 1196 ms 7944 KB Output is correct
8 Correct 1227 ms 8628 KB Output is correct
9 Correct 1793 ms 11124 KB Output is correct
10 Correct 1693 ms 12616 KB Output is correct
11 Correct 1548 ms 12616 KB Output is correct
12 Correct 2354 ms 12512 KB Output is correct
13 Correct 1763 ms 12636 KB Output is correct
14 Correct 853 ms 8240 KB Output is correct
15 Correct 1954 ms 10480 KB Output is correct
16 Correct 3211 ms 13340 KB Output is correct
17 Correct 4203 ms 15644 KB Output is correct
18 Correct 4088 ms 17672 KB Output is correct
19 Correct 3891 ms 18276 KB Output is correct
20 Correct 4347 ms 18056 KB Output is correct
21 Correct 4132 ms 18052 KB Output is correct
22 Correct 2979 ms 17720 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 3 ms 3788 KB Output is correct
6 Correct 2 ms 3788 KB Output is correct
7 Correct 1196 ms 7944 KB Output is correct
8 Correct 1227 ms 8628 KB Output is correct
9 Correct 1793 ms 11124 KB Output is correct
10 Correct 1693 ms 12616 KB Output is correct
11 Correct 1548 ms 12616 KB Output is correct
12 Correct 2354 ms 12512 KB Output is correct
13 Correct 1763 ms 12636 KB Output is correct
14 Correct 853 ms 8240 KB Output is correct
15 Correct 1954 ms 10480 KB Output is correct
16 Correct 3211 ms 13340 KB Output is correct
17 Correct 4203 ms 15644 KB Output is correct
18 Correct 4088 ms 17672 KB Output is correct
19 Correct 3891 ms 18276 KB Output is correct
20 Correct 4347 ms 18056 KB Output is correct
21 Correct 4132 ms 18052 KB Output is correct
22 Correct 2979 ms 17720 KB Output is correct
23 Execution timed out 9083 ms 31580 KB Time limit exceeded
24 Halted 0 ms 0 KB -