Submission #617861

#	Time	Username	Problem	Language	Result	Execution time	Memory
617861		amunduzbaev	Distributing Candies (IOI21_candies)	C++17	0 / 100	5038 ms	25232 KiB

candies

#include "candies.h"

#include "bits/stdc++.h"
using namespace std;

#ifndef EVAL
#include "grader.cpp"
#endif

typedef long long ll;

const ll inf = 1e18;
const int N = 2e5 + 5;

struct ST{
	ll tree[N << 2];
	void set(int i, ll v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) { tree[x] = v; return; }
		int m = (lx + rx) >> 1;
		if(i <= m) set(i, v, lx, m, x << 1);
		else set(i, v, m + 1, rx, x << 1 | 1);
		tree[x] = min(tree[x << 1], tree[x << 1 | 1]);
	}
	
	int get(int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) return lx;
		int m = (lx + rx) >> 1;
		if(tree[x << 1] <= v) return get(v, lx, m, x << 1);
		else return get(v, m + 1, rx, x << 1 | 1);
	}
}tree;

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	int n = c.size();
	int q = l.size();
	
	vector<int> p(n);
	iota(p.begin(), p.end(), 0);
	sort(p.begin(), p.end(), [&](int i, int j){
		return c[i] < c[j];
	});
	
	set<int> ss;
	ss.insert(-1);
	vector<ll> a(q);
	for(int i=0;i<q;i++){
		a[i] = min(a[i], (ll)c[p[0]]);
		a[i] = max(a[i], 0ll);
		a[i] += v[i];
		if(a[i] > c[p[0]]){
			tree.set(i, a[i] - c[p[0]]);
			ss.insert(i);
		} else {
			if(a[i] < 0) ss.insert(i);
			tree.set(i, inf);
		}
		
		if(i + 1 < q) a[i + 1] = a[i];
	}
	
	vector<ll> suff(q + 1);
	for(int i=q-1;~i;i--){
		suff[i] = suff[i + 1] + v[i];
	}
	
	vector<int> res(n);
	for(int i=0;i<n;i++){
		int x = 0;
		if(i) x = c[p[i]] - c[p[i-1]];
		
		if(x){
			int j = tree.get(x);
			while(j < q){
				tree.set(j, inf);
				ss.erase(j);
				auto it = ss.upper_bound(j);
				vector<int> er;
				assert(a[j] <= c[p[i]]);
				int d = (c[p[i]] - a[j]);
				while(it != ss.end()){
					if(a[*it] > c[p[i - 1]]){
						a[*it] += d;
						tree.set(*it, a[*it] - c[p[i - 1]]);
						break;
					} else {
						a[*it] += d;
						if(a[*it] < 0) break;
						er.push_back(*it);
						it++;
					}
				}
				
				for(auto x : er) ss.erase(x);
			}
		}
		
		int last = (*--ss.end());
		res[p[i]] = suff[last + 1];
		if(~last && a[last] >= 0){
			res[p[i]] += c[p[i]];
		}
	}
	
	return res;
}

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