oj.uz

Submission #1021440

# Submission time Handle Problem Language Result Execution time Memory
1021440 2024-07-12T18:16:02 Z mat_jur Dancing Elephants (IOI11_elephants) C++17
100 / 100
 8930 ms 16384 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

int n, l;
vector<int> x;
const int inf = 2'000'000'009;
const int B = 1600;
//const int B = 3;

struct Sqrt {
	int n;
	vector<int> c, e, x, pBucket;
	vector<int> pos;
	vector<vector<int>> buckets;
	int timer;
	int last_buck;

	Sqrt() {}

	Sqrt(vector<int> _x): x(_x), timer(0) {
		n = ssize(x);
		c.resize(n);
		e.resize(n);
		pBucket.resize(n);
		last_buck = (n-1)/B;
		debug(last_buck);
		buckets.resize(last_buck + 1);

		vector<int> idx(n);
		iota(all(idx), 0);
		sort(all(idx), [&](int a, int b) {
			return x[a] < x[b];
		});

		for (int i = 0; i < n; ++i) {
			int j = idx[i];
			buckets[i/B].eb(j); 
			pBucket[j] = i/B;
		}
		for (int i = 0; i <= last_buck; ++i) update_bucket(i);
	}

	void update_bucket(int idx) {
		cerr << "update " << idx << '\n';
		int nxt = ssize(buckets[idx]);
		for (int i = ssize(buckets[idx])-1; i >= 0; --i) {
//			debug(nxt);
			while (nxt-1 >= 0 && x[buckets[idx][nxt-1]] > x[buckets[idx][i]] + l) --nxt;
//			debug(i);
//			debug(buckets[idx][i]);
//			debug(nxt);
			assert(nxt > i);
			c[buckets[idx][i]] = 1 + (nxt < ssize(buckets[idx]) ? c[buckets[idx][nxt]] : 0);
			e[buckets[idx][i]] = (nxt < ssize(buckets[idx]) ? e[buckets[idx][nxt]] : x[buckets[idx][i]] + l);
		}
	}

	void update(int i, int y) {
		++timer;

		auto it = buckets[pBucket[i]].begin();
		while (*it != i) ++it;
		buckets[pBucket[i]].erase(it);
		update_bucket(pBucket[i]);

		x[i] = y;

		int b;
		for (b = 0; b <= last_buck && (buckets[b].empty() || x[buckets[b].back()] <= y); ++b) ;

		if (b > last_buck) --b;

		pBucket[i] = b;
		buckets[b].eb(i);
		int j = ssize(buckets[b]) - 1;
		while (j-1 >= 0 && x[buckets[b][j]] < x[buckets[b][j-1]]) {swap(buckets[b][j], buckets[b][j-1]); --j;}
		update_bucket(b);
	}

	int calc_result() {
//		int res = c[buckets[0][0]], f = e[buckets[0][0]];

		int res = 0, f = -inf;
		for (int j = 0; j <= last_buck; ++j) {
			debug(res);
			debug(f);
			if (buckets[j].empty() || f >= x[buckets[j].back()]) continue;

			int low = -1, high = ssize(buckets[j]);
			while (high-low > 1) {
				int mid = (high + low) / 2;
				if (x[buckets[j][mid]] > f) high = mid;
				else low = mid;
			}

			res += c[buckets[j][high]];
			f = e[buckets[j][high]];
		}

		return res;
	}

	void Debug() {
		debug(buckets);
		debug(x);
		debug(c);
		debug(e);
	}
};

Sqrt q;

void init(int _n, int _l, int _x[]) {
	n = _n; l = _l; 
	for (int i = 0; i < n; ++i) x.eb(_x[i]);
	
	q = Sqrt(x);

	q.Debug();
}

int update(int i, int y) {
	cerr << "NEW UPDATE \n";
	if (q.timer > B) {cerr << "REBUILD \n"; q.Debug(); q = Sqrt(q.x);}

	q.update(i, y);
	q.Debug();
	return q.calc_result();
}

#ifdef LOCAL
int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	int n, l, m;
	cin >> n >> l >> m;
	int *x = new int[n];
	for (int i = 0; i < n; ++i) cin >> x[i];
	init(n, l, x);

	for (int i = 0; i < m; ++i) {
//		int j, y, s;
//		cin >> j >> y >> s;
//		int ans = update(j, y);
//		cout << "ANS = " << ans << ", expected " << s << '\n';
//		if (ans != s) cout << "WA on query " << i+1 << endl;
		int j, y;
		cin >> j >> y;
		cout << update(j, y) << '\n';
	}

	return 0;
}
#endif

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 790 ms 2652 KB Output is correct
8 Correct 743 ms 2972 KB Output is correct
9 Correct 752 ms 5700 KB Output is correct
10 Correct 554 ms 5372 KB Output is correct
11 Correct 554 ms 5188 KB Output is correct
12 Correct 1676 ms 5188 KB Output is correct
13 Correct 575 ms 5020 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 790 ms 2652 KB Output is correct
8 Correct 743 ms 2972 KB Output is correct
9 Correct 752 ms 5700 KB Output is correct
10 Correct 554 ms 5372 KB Output is correct
11 Correct 554 ms 5188 KB Output is correct
12 Correct 1676 ms 5188 KB Output is correct
13 Correct 575 ms 5020 KB Output is correct
14 Correct 845 ms 3908 KB Output is correct
15 Correct 1059 ms 4032 KB Output is correct
16 Correct 2991 ms 6048 KB Output is correct
17 Correct 2803 ms 7348 KB Output is correct
18 Correct 3076 ms 7244 KB Output is correct
19 Correct 1312 ms 7468 KB Output is correct
20 Correct 2817 ms 7316 KB Output is correct
21 Correct 2705 ms 7276 KB Output is correct
22 Correct 1102 ms 6984 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 790 ms 2652 KB Output is correct
8 Correct 743 ms 2972 KB Output is correct
9 Correct 752 ms 5700 KB Output is correct
10 Correct 554 ms 5372 KB Output is correct
11 Correct 554 ms 5188 KB Output is correct
12 Correct 1676 ms 5188 KB Output is correct
13 Correct 575 ms 5020 KB Output is correct
14 Correct 845 ms 3908 KB Output is correct
15 Correct 1059 ms 4032 KB Output is correct
16 Correct 2991 ms 6048 KB Output is correct
17 Correct 2803 ms 7348 KB Output is correct
18 Correct 3076 ms 7244 KB Output is correct
19 Correct 1312 ms 7468 KB Output is correct
20 Correct 2817 ms 7316 KB Output is correct
21 Correct 2705 ms 7276 KB Output is correct
22 Correct 1102 ms 6984 KB Output is correct
23 Correct 4419 ms 15804 KB Output is correct
24 Correct 4804 ms 15812 KB Output is correct
25 Correct 3385 ms 15820 KB Output is correct
26 Correct 3629 ms 16384 KB Output is correct
27 Correct 4313 ms 15668 KB Output is correct
28 Correct 2359 ms 5200 KB Output is correct
29 Correct 2366 ms 5200 KB Output is correct
30 Correct 2360 ms 5412 KB Output is correct
31 Correct 2243 ms 5320 KB Output is correct
32 Correct 3320 ms 15732 KB Output is correct
33 Correct 2883 ms 15128 KB Output is correct
34 Correct 3348 ms 16000 KB Output is correct
35 Correct 2446 ms 16120 KB Output is correct
36 Correct 2056 ms 15804 KB Output is correct
37 Correct 6980 ms 15680 KB Output is correct
38 Correct 3508 ms 14892 KB Output is correct
39 Correct 3834 ms 15508 KB Output is correct
40 Correct 3327 ms 15296 KB Output is correct
41 Correct 8488 ms 15252 KB Output is correct
42 Correct 8930 ms 15460 KB Output is correct