oj.uz

Submission #579965

# Submission time Handle Problem Language Result Execution time Memory
579965 2022-06-20T11:54:02 Z joelau Distributing Candies (IOI21_candies) C++17
100 / 100
 1332 ms 61596 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

tuple<long long,long long,long long> queries[400005];

struct node {
	long long s,e,m,lazy; pair<long long,long long> least,most; node *l, *r;
	node (long long S, long long E) {
		s = S, e = E, m = (s+e)/2, least = make_pair(0,s), most = make_pair(0,s), lazy = 0;
		if (s != e) l = new node(s,m), r = new node(m+1,e);
	}
	void propo() {
		if (lazy == 0) return;
		least.first += lazy, most.first += lazy;
		if (s != e) l->lazy += lazy, r->lazy += lazy;
		lazy = 0;
	}
	void update (long long x, long long y, long long nv) {
		propo();
		if (s == x && e == y) lazy += nv;
		else {
			if (y <= m) l -> update(x,y,nv);
			else if (x > m) r -> update(x,y,nv);
			else l -> update(x,m,nv), r -> update(m+1,y,nv);
			l -> propo(), r -> propo();
			least = min(l->least,r->least), most = max(l->most,r->most);
		}
	}
	pair< pair<long long,long long>, pair<long long,long long> > query (long long x, long long y) {
		propo();
		if (s == x && e == y) return make_pair(least,most);
		else if (y <= m) return l -> query(x,y);
		else if (x > m) return r -> query(x,y);
		else {
			pair< pair<long long,long long>, pair<long long,long long> > q1 = l->query(x,m), q2 = r->query(m+1,y);
			return make_pair(min(q1.first,q2.first),max(q1.second,q2.second));
		}
	}
} *root;

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	long long N = c.size(), Q = l.size();
	for (long long i = 0; i < Q; ++i) queries[i*2] = make_tuple(l[i],i+1,v[i]), queries[i*2+1] = make_tuple(r[i]+1,i+1,-v[i]);
	sort(queries,queries+Q*2);
	root = new node(0,Q);
	vector<int> ans;
	for (long long i = 0, j = 0; i < N; ++i) {
		while (j < Q*2 && get<0>(queries[j]) == i) {
			root -> update(get<1>(queries[j]),Q,get<2>(queries[j]));
			j++;
		}
		long long low = 0, high = Q+1;
		while (high-low > 1) {
			long long mid = (low+high)/2;
			pair< pair<long long,long long>, pair<long long,long long> > q = root -> query(mid,Q);
			if (q.second.first-q.first.first >= c[i]) low = mid;
			else high = mid;
		}
		pair< pair<long long,long long>, pair<long long,long long> > q1 = root -> query(low,Q), q2 = root -> query(Q,Q);
		if (q1.second.first-q1.first.first < c[i]) ans.push_back(q2.first.first - q1.first.first);
		else if (q1.first.second > q1.second.second) {
			if (q1.first.first < q1.second.first) ans.push_back(q2.first.first-q1.first.first);
			else ans.push_back(c[i]-q1.first.first+q2.first.first);
		}
		else {
			if (q1.first.first < q1.second.first) ans.push_back(c[i]-q1.second.first+q2.first.first);
			else ans.push_back(q2.first.first-q1.second.first);
		}
	}
	return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 836 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 5 ms 852 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1117 ms 54736 KB Output is correct
2 Correct 1245 ms 58860 KB Output is correct
3 Correct 1332 ms 58708 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 478 ms 55124 KB Output is correct
3 Correct 239 ms 6680 KB Output is correct
4 Correct 1116 ms 60628 KB Output is correct
5 Correct 1139 ms 61116 KB Output is correct
6 Correct 982 ms 61596 KB Output is correct
7 Correct 947 ms 60648 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 159 ms 54612 KB Output is correct
4 Correct 143 ms 4768 KB Output is correct
5 Correct 600 ms 58132 KB Output is correct
6 Correct 582 ms 58864 KB Output is correct
7 Correct 462 ms 59560 KB Output is correct
8 Correct 628 ms 58056 KB Output is correct
9 Correct 618 ms 59600 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 836 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 1117 ms 54736 KB Output is correct
7 Correct 1245 ms 58860 KB Output is correct
8 Correct 1332 ms 58708 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 478 ms 55124 KB Output is correct
11 Correct 239 ms 6680 KB Output is correct
12 Correct 1116 ms 60628 KB Output is correct
13 Correct 1139 ms 61116 KB Output is correct
14 Correct 982 ms 61596 KB Output is correct
15 Correct 947 ms 60648 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 159 ms 54612 KB Output is correct
19 Correct 143 ms 4768 KB Output is correct
20 Correct 600 ms 58132 KB Output is correct
21 Correct 582 ms 58864 KB Output is correct
22 Correct 462 ms 59560 KB Output is correct
23 Correct 628 ms 58056 KB Output is correct
24 Correct 618 ms 59600 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 165 ms 4628 KB Output is correct
27 Correct 485 ms 54624 KB Output is correct
28 Correct 1190 ms 59280 KB Output is correct
29 Correct 1134 ms 59656 KB Output is correct
30 Correct 1111 ms 59884 KB Output is correct
31 Correct 1060 ms 60084 KB Output is correct
32 Correct 1039 ms 60372 KB Output is correct