Submission #579965

#	Time	Username	Problem	Language	Result	Execution time	Memory
579965		joelau	Distributing Candies (IOI21_candies)	C++17	100 / 100	1332 ms	61596 KiB

candies

#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 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33