Submission #1242867

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242867		AMnu	Distributing Candies (IOI21_candies)	C++20	100 / 100	748 ms	47628 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;

const int MAXN = 2e5+5;
const ll INF = 1e15;

int N, Q;
vector <pii> ch[MAXN];

struct segment {
	int L, R;
	pii val;
	ll lz;
	segment *lef, *rig;
	
	segment(int x,int y) {
		L = x; R = y;
		val.fi = val.se = lz = 0;
		if (L == R) {
			return;
		}
		int mid=(L+R)/2;
		lef = new segment(L,mid);
		rig = new segment(mid+1,R);
	}
	
	pii add(pii x,pii y) {
		return {min(x.fi,y.fi),max(x.se,y.se)};
	}
	
	void push() {
		if (lz) {
			lef->lz += lz;
			lef->val.fi += lz;
			lef->val.se += lz;
			rig->lz += lz;
			rig->val.fi += lz;
			rig->val.se += lz;
			lz = 0;
		}
	}
	
	pii query(int x,int y) {
		if (x <= L && y >= R) {
			return val;
		}
		if (x > R || y < L) {
			return {INF,-INF};
		}
		push();
		return add(lef->query(x,y),rig->query(x,y));
	}
	
	void update(int x,int y,int z) {
		if (x <= L && y >= R) {
			lz += z;
			val.fi += z;
			val.se += z;
			return;
		}
		if (x > R || y < L) {
			return;
		}
		push();
		lef->update(x,y,z);
		rig->update(x,y,z);
		val = add(lef->val,rig->val);
	}
};

vector<int> distribute_candies(vector<int> c,vector<int> l,vector<int> r,vector<int> v) {
	N = c.size();
	Q = v.size();
	for (int i=0;i<Q;i++) {
		ch[l[i]].push_back({i+1,v[i]});
		ch[r[i]+1].push_back({i+1,-v[i]});
	}
	segment tree = segment(0,Q);
	vector <int> s(N);
	for (int i=0;i<N;i++) {
		for (pii x : ch[i]) {
			tree.update(x.fi,Q,x.se);
		}
		int L = 0, R = Q, res = -1;
		while (L <= R) {
			int mid = (L+R)/2;
			pii temp = tree.query(mid,Q);
			if (temp.se - temp.fi > c[i]) {
				res = mid;
				L = mid+1;
			}
			else {
				R = mid-1;
			}
		}
		ll start = tree.query(res,res).fi;
		ll last = tree.query(Q,Q).fi;
		pii val = tree.query(res,Q);
		if (start == val.fi) {
			s[i] = c[i] - val.se + last;
		}
		else {
			s[i] = last - val.fi;
		}
	}
	return s;
}

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33