oj.uz

Submission #448551

# Submission time Handle Problem Language Result Execution time Memory
448551 2021-07-30T14:12:34 Z grt Distributing Candies (IOI21_candies) C++17
100 / 100
 642 ms 36640 KB 
#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back

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;

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

Node T[(1 << 19)];
vi events[nax];

void prop(int v) {
	T[2*v].g += T[v].g;
	T[2*v + 1].g += T[v].g;
	T[v].g = 0;
}

void add(int a, int b, int l, int r, int x, int v) {
	if(a <= l && r <= b) {
		T[v].g += x;
		return;
	}
	prop(v);
	int mid = (l + r) / 2;
	if(a <= mid) add(a, b, l, mid, x, v * 2);
	if(mid < b) add(a, b, mid + 1, r, x, v * 2 + 1);
	T[v].mi = min(T[2*v].mi + T[2*v].g, T[2*v+1].mi + T[2*v+1].g);
	T[v].mx = max(T[2*v].mx + T[2*v].g, T[2*v+1].mx + T[2*v+1].g);
}

tuple<int,ll,ll> ask(int d) {
	int v = 1, l = 0, r = q - 1;
	ll mi = INF, mx = -INF;
	while(l < r) {
		T[v].mi += T[v].g;
		T[v].mx += T[v].g;
		prop(v);
		//cout << l << " " << r << "\n";
		int mid = (l + r) / 2;
		if(max(mx, T[2 * v + 1].mx + T[2*v+1].g) - min(mi, T[2 * v + 1].mi + T[2*v + 1].g) > d) {
			v = v * 2 + 1;
			l = mid + 1;
		} else {
			mx = max(mx, T[2 * v + 1].mx + T[2*v + 1].g);
			mi = min(mi, T[2 * v + 1].mi + T[2*v + 1].g);
			v = v * 2;
			r = mid;
		}
	}
	mi = min(mi, T[v].g + T[v].mi);
	mx = max(mx, T[v].g + T[v].mx);
	return {l, mi, mx};
}

pair<ll,ll>qr(int a, int b, int l, int r, int v) {
	if(a <= l && r <= b) {
		return {T[v].mi + T[v].g, T[v].mx + T[v].g};
	}
	int mid = (l + r) / 2;
	prop(v);
	pair<ll,ll>w = {INF, -INF};
	if(a <= mid) {
		auto y = qr(a, b, l, mid, v * 2);
		w = {min(w.ST, y.ST), max(w.ND, y.ND)};
	}
	if(mid < b) {
		auto y = qr(a, b, mid + 1, r, v * 2 + 1);
		w = {min(w.ST, y.ST), max(w.ND, y.ND)};
	}
	T[v].mi = min(T[2*v].mi + T[2*v].g, T[2*v+1].mi + T[2*v+1].g);
	T[v].mx = max(T[2*v].mx + T[2*v].g, T[2*v+1].mx + T[2*v+1].g);
	return w;
}




vi distribute_candies(vi c, vi la, vi ra, vi v) {
	n = (int)c.size();
	q = (int)la.size();
	for(int i = 0; i < q; ++i) {
		events[la[i]].PB(i + 1);
		events[ra[i] + 1].PB(-i - 1);
	}
	q++;
	vi ans(n);
	for(int i = 0; i < n; ++i) {
		for(int x : events[i]) {
			if(x > 0) {
				add(x, q - 1, 0, q - 1, v[x - 1], 1);
			} else {
				x = -x;
				add(x, q - 1, 0, q - 1, -v[x - 1], 1);
			}
		}
		auto [pos, mi, mx] = ask(c[i]);
		//cout << pos << " " << mi << " " << mx << "\n";
		auto zz = qr(q - 1, q - 1, 0, q - 1, 1);
		if(mx - mi <= c[i]) {
			auto z2 = qr(0, q - 1, 0, q - 1, 1);
			ans[i] = zz.ST - z2.ST;
		} else {
			auto z = qr(pos + 1, q - 1, 0, q - 1, 1);
			if(mi < z.ST) {
				ans[i] = c[i] - (z.ND - zz.ST);
			} else {
				ans[i] = zz.ST - z.ST;
			}
		}
		
	}
	return ans;
}

//int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	//int N, Q;
	//cin >> N >> Q;
	//vi c(N), l(Q), r(Q), v(Q);
	//for(int i = 0; i < N; ++i) {
		//cin >> c[i];
	//}
	//for(int i = 0; i < Q; ++i) {
		//cin >> l[i] >> r[i] >> v[i];
	//}
	//auto ans = distribute_candies(c,l,r,v);
	//for(int x : ans) cout << x << " ";
//}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 3 ms 4996 KB Output is correct
3 Correct 5 ms 5196 KB Output is correct
4 Correct 5 ms 5196 KB Output is correct
5 Correct 6 ms 5260 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 618 ms 30020 KB Output is correct
2 Correct 637 ms 34012 KB Output is correct
3 Correct 642 ms 33860 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 275 ms 24480 KB Output is correct
3 Correct 141 ms 8868 KB Output is correct
4 Correct 614 ms 30084 KB Output is correct
5 Correct 603 ms 36244 KB Output is correct
6 Correct 626 ms 36640 KB Output is correct
7 Correct 590 ms 35972 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 130 ms 23704 KB Output is correct
4 Correct 139 ms 7604 KB Output is correct
5 Correct 361 ms 26220 KB Output is correct
6 Correct 331 ms 26284 KB Output is correct
7 Correct 344 ms 26356 KB Output is correct
8 Correct 315 ms 26228 KB Output is correct
9 Correct 326 ms 26428 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 3 ms 4996 KB Output is correct
3 Correct 5 ms 5196 KB Output is correct
4 Correct 5 ms 5196 KB Output is correct
5 Correct 6 ms 5260 KB Output is correct
6 Correct 618 ms 30020 KB Output is correct
7 Correct 637 ms 34012 KB Output is correct
8 Correct 642 ms 33860 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 275 ms 24480 KB Output is correct
11 Correct 141 ms 8868 KB Output is correct
12 Correct 614 ms 30084 KB Output is correct
13 Correct 603 ms 36244 KB Output is correct
14 Correct 626 ms 36640 KB Output is correct
15 Correct 590 ms 35972 KB Output is correct
16 Correct 4 ms 4940 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Correct 130 ms 23704 KB Output is correct
19 Correct 139 ms 7604 KB Output is correct
20 Correct 361 ms 26220 KB Output is correct
21 Correct 331 ms 26284 KB Output is correct
22 Correct 344 ms 26356 KB Output is correct
23 Correct 315 ms 26228 KB Output is correct
24 Correct 326 ms 26428 KB Output is correct
25 Correct 3 ms 4996 KB Output is correct
26 Correct 152 ms 8780 KB Output is correct
27 Correct 273 ms 26948 KB Output is correct
28 Correct 558 ms 34492 KB Output is correct
29 Correct 577 ms 34880 KB Output is correct
30 Correct 587 ms 35072 KB Output is correct
31 Correct 587 ms 35276 KB Output is correct
32 Correct 577 ms 35468 KB Output is correct