oj.uz

Submission #947322

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

int n, l;
const int N = 150'005, B = 400;
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;
}
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();
}
#ifdef MINA
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int _n, _l;
	cin >> _n >> _l;
	int _a[_n];
	for (int i = 0; i < _n; i++) {
		cin >> _a[i];
	}
	init(_n, _l, _a);
	int _q;
	cin >> _q;
	while (_q--) {
		int _i, _y;
		cin >> _i >> _y;
		cout << update(_i, _y) << '\n';
	}
	return 0;
}
#endif

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 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 6488 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 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 6488 KB Output is correct
7 Correct 195 ms 9120 KB Output is correct
8 Correct 207 ms 9300 KB Output is correct
9 Correct 234 ms 9816 KB Output is correct
10 Correct 3208 ms 11044 KB Output is correct
11 Correct 3320 ms 10624 KB Output is correct
12 Correct 3908 ms 10708 KB Output is correct
13 Correct 3184 ms 10780 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 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 6488 KB Output is correct
7 Correct 195 ms 9120 KB Output is correct
8 Correct 207 ms 9300 KB Output is correct
9 Correct 234 ms 9816 KB Output is correct
10 Correct 3208 ms 11044 KB Output is correct
11 Correct 3320 ms 10624 KB Output is correct
12 Correct 3908 ms 10708 KB Output is correct
13 Correct 3184 ms 10780 KB Output is correct
14 Correct 3686 ms 10492 KB Output is correct
15 Correct 323 ms 9600 KB Output is correct
16 Correct 642 ms 10072 KB Output is correct
17 Correct 1801 ms 11324 KB Output is correct
18 Correct 3638 ms 10996 KB Output is correct
19 Correct 7787 ms 11664 KB Output is correct
20 Correct 1902 ms 11200 KB Output is correct
21 Correct 7399 ms 11148 KB Output is correct
22 Correct 6351 ms 11816 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 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 6488 KB Output is correct
7 Correct 195 ms 9120 KB Output is correct
8 Correct 207 ms 9300 KB Output is correct
9 Correct 234 ms 9816 KB Output is correct
10 Correct 3208 ms 11044 KB Output is correct
11 Correct 3320 ms 10624 KB Output is correct
12 Correct 3908 ms 10708 KB Output is correct
13 Correct 3184 ms 10780 KB Output is correct
14 Correct 3686 ms 10492 KB Output is correct
15 Correct 323 ms 9600 KB Output is correct
16 Correct 642 ms 10072 KB Output is correct
17 Correct 1801 ms 11324 KB Output is correct
18 Correct 3638 ms 10996 KB Output is correct
19 Correct 7787 ms 11664 KB Output is correct
20 Correct 1902 ms 11200 KB Output is correct
21 Correct 7399 ms 11148 KB Output is correct
22 Correct 6351 ms 11816 KB Output is correct
23 Correct 1487 ms 16480 KB Output is correct
24 Correct 1566 ms 16976 KB Output is correct
25 Correct 1184 ms 16208 KB Output is correct
26 Execution timed out 9038 ms 16284 KB Time limit exceeded
27 Halted 0 ms 0 KB -