oj.uz

Submission #1021399

# Submission time Handle Problem Language Result Execution time Memory
1021399 2024-07-12T17:33:42 Z mat_jur Dancing Elephants (IOI11_elephants) C++17
26 / 100
 17 ms 2396 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#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 = 400;

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;
		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() || 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]];

		for (int j = 1; j <= last_buck; ++j) {
			if (buckets[j].empty() || f >= 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(calc_result());
		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) q = Sqrt(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;
	}

	return 0;
}
#endif

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 17 ms 2396 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 17 ms 2396 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 17 ms 2396 KB Output isn't correct
8 Halted 0 ms 0 KB -