oj.uz

Submission #947314

# Submission time Handle Problem Language Result Execution time Memory
947314 2024-03-15T21:49:36 Z MinaRagy06 Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 21824 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define SZ(x) (int) x.size()

int n, l;
struct block {
	int n;
	vector<int> v;
	vector<array<int, 2>> dp;
	void build() {
		n = v.size();
		dp.resize(n);
		int p = n;
		for (int i = n - 1; i >= 0; i--) {
			while (p - 1 >= 0 && v[p - 1] >= v[i] + l) {
				p--;
			}
			if (v[i] + l <= v.back()) {
				dp[i] = {dp[p][0] + 1, dp[p][1]};
			} else {
				dp[i] = {1, v[i] + l};
			}
		}
	}
	void insert(int x) {
		v.push_back(x);
		for (int i = v.size() - 1; i - 1 >= 0; i--) {
			if (v[i] <= v[i - 1]) {
				swap(v[i], v[i - 1]);
			} else {
				break;
			}
		}
		build();
	}
	void erase(int x) {
		bool done = 0;
		vector<int> newv;
		for (int i = 0; i < SZ(v); i++) {
			if (!done && v[i] == x) {
				done = 1;
				continue;
			}
			newv.push_back(v[i]);
		}
		v = newv;
		build();
	}
	block(vector<int> &_v) {
		v = _v;
		n = v.size();
		build();
	}
};
vector<block> b;
void insert(int x) {
	for (int i = 0; i < SZ(b); i++) {
		if (i == SZ(b) - 1 || (b[i].v.back() <= x && x <= b[i + 1].v[0]) || (x <= b[i].v.back())) {
			b[i].insert(x);
			break;
		}
	}
}
void erase(int x) {
	for (int i = 0; i < SZ(b); i++) {
		if (b[i].v.empty()) continue;
		if (b[i].v[0] <= x && x <= b[i].v.back()) {
			b[i].erase(x);
			break;
		}
	}
}
int query() {
	int ans = 0, prv = 0;
	for (int i = 0; i < SZ(b); i++) {
		if (b[i].v.empty()) continue;
		if (prv <= b[i].v.back()) {
			int p = lower_bound(b[i].v.begin(), b[i].v.end(), prv) - b[i].v.begin();
			ans += b[i].dp[p][0];
			prv = b[i].dp[p][1];
		}
	}
	return ans;
}
const int N = 150'005, B = 200;
vector<int> a;
void build() {
	vector<int> cur;
	for (int i = 0; i < n; i++) {
		if (cur.size() == B) {
			b.push_back(cur);
			cur.clear();
		}
		cur.push_back(a[i]);
	}
	b.push_back(cur);	
}
void rebuild() {
	a.clear();
	for (int i = 0; i < SZ(b); i++) {
		for (auto j : b[i].v) {
			a.push_back(j);
		}
	}
	b.clear();
	build();
}
void init(int _n, int _l, int _a[]) {
	n = _n, l = _l + 1;
	a.resize(n);
	for (int i = 0; i < n; i++) {
		a[i] = _a[i];
	}
	build();
}
int cnt = 0;
int update(int x, int y) {
	if (cnt == B) {
		rebuild();
		cnt = 0;
	}
	erase(a[x]);
	a[x] = y;
	insert(y);
	return query();
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6592 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6588 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6592 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6588 KB Output is correct
7 Correct 127 ms 9964 KB Output is correct
8 Correct 152 ms 10360 KB Output is correct
9 Correct 220 ms 11348 KB Output is correct
10 Correct 3233 ms 12036 KB Output is correct
11 Correct 3277 ms 12628 KB Output is correct
12 Correct 4292 ms 12368 KB Output is correct
13 Correct 3287 ms 11784 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6592 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6588 KB Output is correct
7 Correct 127 ms 9964 KB Output is correct
8 Correct 152 ms 10360 KB Output is correct
9 Correct 220 ms 11348 KB Output is correct
10 Correct 3233 ms 12036 KB Output is correct
11 Correct 3277 ms 12628 KB Output is correct
12 Correct 4292 ms 12368 KB Output is correct
13 Correct 3287 ms 11784 KB Output is correct
14 Correct 3677 ms 11604 KB Output is correct
15 Correct 241 ms 11092 KB Output is correct
16 Correct 466 ms 11864 KB Output is correct
17 Correct 1753 ms 13388 KB Output is correct
18 Correct 3514 ms 12804 KB Output is correct
19 Correct 7659 ms 13884 KB Output is correct
20 Correct 1853 ms 13416 KB Output is correct
21 Correct 7329 ms 12908 KB Output is correct
22 Correct 6227 ms 13412 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6592 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6588 KB Output is correct
7 Correct 127 ms 9964 KB Output is correct
8 Correct 152 ms 10360 KB Output is correct
9 Correct 220 ms 11348 KB Output is correct
10 Correct 3233 ms 12036 KB Output is correct
11 Correct 3277 ms 12628 KB Output is correct
12 Correct 4292 ms 12368 KB Output is correct
13 Correct 3287 ms 11784 KB Output is correct
14 Correct 3677 ms 11604 KB Output is correct
15 Correct 241 ms 11092 KB Output is correct
16 Correct 466 ms 11864 KB Output is correct
17 Correct 1753 ms 13388 KB Output is correct
18 Correct 3514 ms 12804 KB Output is correct
19 Correct 7659 ms 13884 KB Output is correct
20 Correct 1853 ms 13416 KB Output is correct
21 Correct 7329 ms 12908 KB Output is correct
22 Correct 6227 ms 13412 KB Output is correct
23 Correct 1993 ms 21824 KB Output is correct
24 Correct 1894 ms 21764 KB Output is correct
25 Correct 1686 ms 21556 KB Output is correct
26 Execution timed out 9097 ms 21176 KB Time limit exceeded
27 Halted 0 ms 0 KB -