Submission #617876

#	Time	Username	Problem	Language	Result	Execution time	Memory
617876		amunduzbaev	Distributing Candies (IOI21_candies)	C++17	0 / 100	472 ms	29668 KiB

candies

#include "candies.h"

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

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

typedef long long ll;
#define ar array

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);
	}
	
	ll mn(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return inf;
		if(lx >= l && rx <= r) return tree[x];
		int m = (lx + rx) >> 1;
		return min(mn(l, r, lx, m, x << 1), mn(l, r, m + 1, rx, x << 1 | 1));
	}
}tree, T;

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;
	set<ar<int, 2>> tt;
	ss.insert(-1);
	vector<ll> a(q);
	for(int i=0;i<q;i++){
		tree.set(i, inf), T.set(i, inf);
		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]);
			ss.insert(i);
		} else if(a[i] < 0){
			if(!ss.empty() && a[(*--ss.end())] >= 0){
				T.set(i, 0 - a[i]);
			}
			ss.insert(i);
		}
		
		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 j = tree.get(c[p[i]]);
		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]);
					break;
				} else {
					a[*it] += d;
					if(T.mn(*it, *it) != inf) T.set(*it, 0 - a[*it]);
					if(a[*it] < 0) break;
					er.push_back(*it);
					it++;
				}
			}
			
			for(auto x : er){
				T.set(x, inf);
				ss.erase(x);
			}
			
			j = tree.get(c[p[i]]);
		}
		
		j = T.get(c[p[i]] - c[p[0]]);
		while(j < q){
			ss.erase(j);
			T.set(j, inf);
			auto it = ss.upper_bound(j);
			if(it != ss.end() && a[*it] < 0){
				T.set(*it, 0 - a[*it]);
			}
			
			j = T.get(c[p[i]] - c[p[0]]);
		}
		
		//~ for(auto x : ss) cout<<x<<" ";
		//~ cout<<"\n";
		assert(!ss.empty());
		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