oj.uz

Submission #536018

# Submission time Handle Problem Language Result Execution time Memory
536018 2022-03-12T06:47:20 Z grt Distributing Candies (IOI21_candies) C++17
100 / 100
 540 ms 38092 KB 
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second

//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

const int nax = 200 * 1000 + 10;
const ll INF = 1e18;
int n, q;
vector<pi>evs[nax];

struct Node {
	ll g, mi, mx;
};

Node T[(1 << 19)];

void puttag(int v, ll x) {
	T[v].mi += x;
	T[v].mx += x;
	T[v].g += x;
}

void push(int v) {
	puttag(v << 1, T[v].g);
	puttag(v << 1 | 1, T[v].g);
	T[v].g = 0;
}

void merge(int v) {
	T[v].mi = min(T[v << 1].mi, T[v << 1 | 1].mi) + T[v].g;
	T[v].mx = max(T[v << 1].mx, T[v << 1 | 1].mx) + T[v].g;
}

void upd(int a, int b, ll x, int l = 0, int r = q, int v = 1) {
	if(a <= l && r <= b) {
		puttag(v, x);
		return;
	}
	push(v);
	int mid = (l + r) >> 1;
	if(a <= mid) upd(a, b, x, l, mid, v << 1);
	if(mid < b) upd(a, b, x, mid + 1, r, v << 1 | 1);
	merge(v);
}

tuple<int,ll,ll,ll> ask(int k) {
	int v = 1, l = 0, r = q;
	ll mi = INF, mx = -INF;
	while(l != r) {
		int mid = (l + r) >> 1;
		push(v);
		if(max(mx, T[v << 1 | 1].mx) - min(mi, T[v << 1 | 1].mi) > k) {
			v = v << 1 | 1;
			l = mid + 1;
		} else {
			mx = max(mx, T[v << 1 | 1].mx);
			mi = min(mi, T[v << 1 | 1].mi);
			v = v << 1;
			r = mid;
		}
	}
	mi = min(mi, T[v].mi);
	mx = max(mx, T[v].mx);
	return {l, mi, mx, T[v].mi};
}

vi distribute_candies(vi _c, vi _l, vi _r, vi _v) {
	n = (int)_c.size();
	q = (int)_l.size();
	for(int i = 0; i < q; ++i) {
		evs[_l[i]].emplace_back(i + 1, _v[i]);
		evs[_r[i] + 1].emplace_back(i + 1, -_v[i]);
	}
	vi ans(n);
	ll sum = 0;
	for(int i = 0; i < n; ++i) {
		for(auto &[a,b] : evs[i]) {
			upd(a, q, b);
			sum += b;
		}
		auto [p, a, b, val] = ask(_c[i]);
		if(b - a <= _c[i]) {
			ans[i] = sum - a;
		} else {
			if(val == a) {
				//cerr << _c[i] + sum - b << "\n";
				ans[i] = _c[i] + sum - b;
			} else {
				assert(val == b);
				//cerr << sum - a << "\n";
				ans[i] = sum - a;
			}
		}
	}
	return ans;
}

//int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	//distribute_candies({10, 15, 13}, {0, 0}, {2, 1}, {20, -11});
//}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 5 ms 5204 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 31392 KB Output is correct
2 Correct 540 ms 35460 KB Output is correct
3 Correct 479 ms 35300 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 262 ms 26572 KB Output is correct
3 Correct 89 ms 9584 KB Output is correct
4 Correct 475 ms 32320 KB Output is correct
5 Correct 445 ms 37640 KB Output is correct
6 Correct 498 ms 38092 KB Output is correct
7 Correct 512 ms 37432 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4944 KB Output is correct
3 Correct 129 ms 25248 KB Output is correct
4 Correct 84 ms 7684 KB Output is correct
5 Correct 248 ms 27460 KB Output is correct
6 Correct 234 ms 27504 KB Output is correct
7 Correct 211 ms 27572 KB Output is correct
8 Correct 207 ms 27580 KB Output is correct
9 Correct 229 ms 27560 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 5 ms 5204 KB Output is correct
6 Correct 426 ms 31392 KB Output is correct
7 Correct 540 ms 35460 KB Output is correct
8 Correct 479 ms 35300 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 262 ms 26572 KB Output is correct
11 Correct 89 ms 9584 KB Output is correct
12 Correct 475 ms 32320 KB Output is correct
13 Correct 445 ms 37640 KB Output is correct
14 Correct 498 ms 38092 KB Output is correct
15 Correct 512 ms 37432 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 4 ms 4944 KB Output is correct
18 Correct 129 ms 25248 KB Output is correct
19 Correct 84 ms 7684 KB Output is correct
20 Correct 248 ms 27460 KB Output is correct
21 Correct 234 ms 27504 KB Output is correct
22 Correct 211 ms 27572 KB Output is correct
23 Correct 207 ms 27580 KB Output is correct
24 Correct 229 ms 27560 KB Output is correct
25 Correct 4 ms 5004 KB Output is correct
26 Correct 75 ms 8808 KB Output is correct
27 Correct 280 ms 29092 KB Output is correct
28 Correct 506 ms 35840 KB Output is correct
29 Correct 460 ms 36236 KB Output is correct
30 Correct 480 ms 36408 KB Output is correct
31 Correct 454 ms 36716 KB Output is correct
32 Correct 455 ms 36908 KB Output is correct