oj.uz

Submission #947316

# Submission time Handle Problem Language Result Execution time Memory
947316 2024-03-15T21:51:33 Z MinaRagy06 Dancing Elephants (IOI11_elephants) C++17
50 / 100
 9000 ms 11436 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define ll long long
#define SZ(x) (int) x.size()

int n, l;
const int N = 150'005, B = 350;
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 1 ms 6492 KB Output is correct
2 Correct 1 ms 6596 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 6596 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 1 ms 6492 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 6596 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 198 ms 9052 KB Output is correct
8 Correct 207 ms 9300 KB Output is correct
9 Correct 256 ms 10068 KB Output is correct
10 Correct 2890 ms 10852 KB Output is correct
11 Correct 2856 ms 10984 KB Output is correct
12 Correct 4740 ms 10640 KB Output is correct
13 Correct 2815 ms 11128 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6596 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 198 ms 9052 KB Output is correct
8 Correct 207 ms 9300 KB Output is correct
9 Correct 256 ms 10068 KB Output is correct
10 Correct 2890 ms 10852 KB Output is correct
11 Correct 2856 ms 10984 KB Output is correct
12 Correct 4740 ms 10640 KB Output is correct
13 Correct 2815 ms 11128 KB Output is correct
14 Correct 4213 ms 9992 KB Output is correct
15 Correct 329 ms 9464 KB Output is correct
16 Correct 640 ms 10400 KB Output is correct
17 Correct 2053 ms 11436 KB Output is correct
18 Correct 4162 ms 10936 KB Output is correct
19 Execution timed out 9021 ms 11436 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6596 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 198 ms 9052 KB Output is correct
8 Correct 207 ms 9300 KB Output is correct
9 Correct 256 ms 10068 KB Output is correct
10 Correct 2890 ms 10852 KB Output is correct
11 Correct 2856 ms 10984 KB Output is correct
12 Correct 4740 ms 10640 KB Output is correct
13 Correct 2815 ms 11128 KB Output is correct
14 Correct 4213 ms 9992 KB Output is correct
15 Correct 329 ms 9464 KB Output is correct
16 Correct 640 ms 10400 KB Output is correct
17 Correct 2053 ms 11436 KB Output is correct
18 Correct 4162 ms 10936 KB Output is correct
19 Execution timed out 9021 ms 11436 KB Time limit exceeded
20 Halted 0 ms 0 KB -