oj.uz

Submission #947318

# Submission time Handle Problem Language Result Execution time Memory
947318 2024-03-15T21:52:50 Z MinaRagy06 Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 16564 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 = 300;
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();
}

Subtask #1
10.0 / 10.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 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 2 ms 6488 KB Output is correct
7 Correct 162 ms 9088 KB Output is correct
8 Correct 181 ms 9544 KB Output is correct
9 Correct 213 ms 9808 KB Output is correct
10 Correct 3110 ms 11156 KB Output is correct
11 Correct 3250 ms 10852 KB Output is correct
12 Correct 4208 ms 10436 KB Output is correct
13 Correct 3116 ms 11064 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 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 2 ms 6488 KB Output is correct
7 Correct 162 ms 9088 KB Output is correct
8 Correct 181 ms 9544 KB Output is correct
9 Correct 213 ms 9808 KB Output is correct
10 Correct 3110 ms 11156 KB Output is correct
11 Correct 3250 ms 10852 KB Output is correct
12 Correct 4208 ms 10436 KB Output is correct
13 Correct 3116 ms 11064 KB Output is correct
14 Correct 3701 ms 10060 KB Output is correct
15 Correct 276 ms 9456 KB Output is correct
16 Correct 550 ms 10248 KB Output is correct
17 Correct 1730 ms 11832 KB Output is correct
18 Correct 3495 ms 10860 KB Output is correct
19 Correct 7771 ms 11548 KB Output is correct
20 Correct 1812 ms 11484 KB Output is correct
21 Correct 7200 ms 11524 KB Output is correct
22 Correct 6041 ms 11780 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 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 2 ms 6488 KB Output is correct
7 Correct 162 ms 9088 KB Output is correct
8 Correct 181 ms 9544 KB Output is correct
9 Correct 213 ms 9808 KB Output is correct
10 Correct 3110 ms 11156 KB Output is correct
11 Correct 3250 ms 10852 KB Output is correct
12 Correct 4208 ms 10436 KB Output is correct
13 Correct 3116 ms 11064 KB Output is correct
14 Correct 3701 ms 10060 KB Output is correct
15 Correct 276 ms 9456 KB Output is correct
16 Correct 550 ms 10248 KB Output is correct
17 Correct 1730 ms 11832 KB Output is correct
18 Correct 3495 ms 10860 KB Output is correct
19 Correct 7771 ms 11548 KB Output is correct
20 Correct 1812 ms 11484 KB Output is correct
21 Correct 7200 ms 11524 KB Output is correct
22 Correct 6041 ms 11780 KB Output is correct
23 Correct 1589 ms 16564 KB Output is correct
24 Correct 1601 ms 16560 KB Output is correct
25 Correct 1251 ms 15956 KB Output is correct
26 Execution timed out 9041 ms 16300 KB Time limit exceeded
27 Halted 0 ms 0 KB -