Submission #1021440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021440		mat_jur	Dancing Elephants (IOI11_elephants)	C++17	100 / 100	8930 ms	16384 KiB

elephants

#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 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3