oj.uz

Submission #529386

# Submission time Handle Problem Language Result Execution time Memory
529386 2022-02-22T23:21:13 Z flappybird Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 28056 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;
	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 2 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 2 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 1221 ms 8108 KB Output is correct
8 Correct 1259 ms 8792 KB Output is correct
9 Correct 1573 ms 11508 KB Output is correct
10 Correct 1175 ms 12748 KB Output is correct
11 Correct 1156 ms 12932 KB Output is correct
12 Correct 2146 ms 12856 KB Output is correct
13 Correct 1136 ms 12860 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 2 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 1221 ms 8108 KB Output is correct
8 Correct 1259 ms 8792 KB Output is correct
9 Correct 1573 ms 11508 KB Output is correct
10 Correct 1175 ms 12748 KB Output is correct
11 Correct 1156 ms 12932 KB Output is correct
12 Correct 2146 ms 12856 KB Output is correct
13 Correct 1136 ms 12860 KB Output is correct
14 Correct 891 ms 8452 KB Output is correct
15 Correct 1920 ms 10620 KB Output is correct
16 Correct 2863 ms 13288 KB Output is correct
17 Correct 3481 ms 16084 KB Output is correct
18 Correct 3565 ms 16160 KB Output is correct
19 Correct 3702 ms 16504 KB Output is correct
20 Correct 3718 ms 16560 KB Output is correct
21 Correct 3582 ms 16620 KB Output is correct
22 Correct 1624 ms 16704 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 2 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 1221 ms 8108 KB Output is correct
8 Correct 1259 ms 8792 KB Output is correct
9 Correct 1573 ms 11508 KB Output is correct
10 Correct 1175 ms 12748 KB Output is correct
11 Correct 1156 ms 12932 KB Output is correct
12 Correct 2146 ms 12856 KB Output is correct
13 Correct 1136 ms 12860 KB Output is correct
14 Correct 891 ms 8452 KB Output is correct
15 Correct 1920 ms 10620 KB Output is correct
16 Correct 2863 ms 13288 KB Output is correct
17 Correct 3481 ms 16084 KB Output is correct
18 Correct 3565 ms 16160 KB Output is correct
19 Correct 3702 ms 16504 KB Output is correct
20 Correct 3718 ms 16560 KB Output is correct
21 Correct 3582 ms 16620 KB Output is correct
22 Correct 1624 ms 16704 KB Output is correct
23 Execution timed out 9055 ms 28056 KB Time limit exceeded
24 Halted 0 ms 0 KB -