oj.uz

Submission #947323

# Submission time Handle Problem Language Result Execution time Memory
947323 2024-03-15T21:56:22 Z MinaRagy06 Dancing Elephants (IOI11_elephants) C++17
26 / 100
 304 ms 9812 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);
	cnt++;
	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 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 1 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 1 ms 6492 KB Output is correct

Subtask #3
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 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 6492 KB Output is correct
7 Correct 213 ms 8796 KB Output is correct
8 Correct 228 ms 9092 KB Output is correct
9 Correct 304 ms 9812 KB Output is correct
10 Incorrect 135 ms 9656 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
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 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 6492 KB Output is correct
7 Correct 213 ms 8796 KB Output is correct
8 Correct 228 ms 9092 KB Output is correct
9 Correct 304 ms 9812 KB Output is correct
10 Incorrect 135 ms 9656 KB Output isn't correct
11 Halted 0 ms 0 KB -

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 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 6492 KB Output is correct
7 Correct 213 ms 8796 KB Output is correct
8 Correct 228 ms 9092 KB Output is correct
9 Correct 304 ms 9812 KB Output is correct
10 Incorrect 135 ms 9656 KB Output isn't correct
11 Halted 0 ms 0 KB -