Submission #602049

#	Time	Username	Problem	Language	Result	Execution time	Memory
602049		SeDunion	Distributing Candies (IOI21_candies)	C++17	100 / 100	1984 ms	55868 KiB

candies

#include "candies.h"
#include<algorithm>
#include<iostream>
#include <vector>

using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;

const int N = 1e6 + 123; 
const ll inf = 1e18;

ll tmn[N << 2], tmx[N << 2];
ll p[N << 2];

int n, q;

void push(int v, int l, int r) {
	if (!p[v]) return;
	tmn[v] += p[v], tmx[v] += p[v];
	if (r - l > 1) p[v << 1] += p[v], p[v<<1|1] += p[v];
	p[v] = 0;
}

void upd1(int L, int R, ll val, int l = 0, int r = q + 1, int v = 1) {
	push(v, l, r);
	if (L <= l && r <= R) {
		p[v] += val;
		push(v, l, r);
		return;
	}
	if (L >= r || l >= R) return;
	int m = (l + r) >> 1;
	upd1(L, R, val, l, m, v << 1);
	upd1(L, R, val, m, r, v<<1|1);
	tmn[v] = min(tmn[v << 1], tmn[v<<1|1]);
	tmx[v] = max(tmx[v << 1], tmx[v<<1|1]);
}


ll gmn1(int L, int R, int l = 0, int r = q + 1, int v = 1) {
	push(v, l, r);
	if (L <= l && r <= R) return tmn[v];
	if (L >= r || l >= R) return inf;
	int m = (l + r) >> 1;
	return min(gmn1(L, R, l, m, v << 1), gmn1(L, R, m, r, v<<1|1));
}

ll gmx1(int L, int R, int l = 0, int r = q + 1, int v = 1) {
	push(v, l, r);
	if (L <= l && r <= R) return tmx[v];
	if (L >= r || l >= R) return -inf;
	int m = (l + r) >> 1;
	return max(gmx1(L, R, l, m, v << 1), gmx1(L, R, m, r, v<<1|1));
}

void upd(int l, int r, ll val) {
	upd1(l + 1, r + 1, val);
}

ll gmn(int l, int r) { return gmn1(l, r + 1); }
ll gmx(int l, int r) { return gmx1(l, r + 1); }

vector<int>ev[N];

vi distribute_candies(vi c, vi l, vi r, vi v) {
	n = c.size();
	q = l.size();
	vector<int>ans;
	for (int i = 0 ; i < q ; ++ i) ev[l[i]].emplace_back(i), ev[r[i]+1].emplace_back(i);
	for (int i = 0 ; i < n ; ++ i) {
		//cout << " ---\n" << i << "\n-\n";
		for (int j : ev[i]) {
			if (l[j] == i) {
				//cout << "adding " << j << " " << v[j] << endl;
				upd(j, q, +v[j]);
			} else {
				//cout << "deleting " << j << " " << v[j] << endl;
				upd(j, q, -v[j]);
			}
		}
		int l = 0, r = q - 1;
		int o = -1;
		while (l <= r) {
			int k = (l + r) >> 1;
			ll mx = gmx(k, q), mn = gmn(k, q);
			//cout << k << " " << mx << " " << mn << endl;
			if (mx - mn >= c[i]) {
				l = k + 1;
				o = k;
			} else {
				r = k - 1;
			}
		}
		if (o == -1) {
			//cout << i << " e\n";
			ans.emplace_back(gmx(q, q) - gmn(0, q));
			continue;
		}
		ll s;
		if (gmx(o, q) == gmx(o + 1, q)) s = gmx(o + 1, q) - c[i];
		else s = gmn(o + 1, q);
		//cout << i << " " << o << " " << s << endl;
		ans.emplace_back(gmx(q, q) - s);
	}
	return ans;
}

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