Submission #837689

#	Time	Username	Problem	Language	Result	Execution time	Memory
837689		NothingXD	Distributing Candies (IOI21_candies)	C++17	67 / 100	539 ms	38880 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2")

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 2e5 + 10;
const ll inf = 1e18;
int n, q, c[maxn];
vector<pii> Q[maxn];
pll seg[maxn << 2];
ll lazy[maxn << 2];

pll operator +(pll a, pll b){
	return MP(min(a.F, b.F), max(a.S, b.S));
}

void shift(int v, int l, int r);

void add(int v, int l, int r, int ql, int qr, ll val){
	if (qr <= l || r <= ql) return;
	if (ql <= l && r <= qr){
		seg[v].F += val;
		seg[v].S += val;
		lazy[v] += val;
		return;
	}
	shift(v, l, r);
	int mid = (l + r) / 2;
	add(v << 1, l, mid, ql, qr, val);
	add(v << 1 | 1, mid, r, ql, qr, val);
	seg[v] = seg[v << 1] + seg[v << 1 | 1];
}

int find(int v, int l, int r, int val, pll &suf){
	//debug(v, l, r, val, seg[v].S, suf.S, seg[v].F, suf.F);
	if (max(seg[v].S, suf.S) - min(seg[v].F, suf.F) < val){
		suf = suf + seg[v];
		return -1;
	}
	if (l + 1 == r){
		suf = suf + seg[v];
		return l;
	}
	shift(v, l, r);
	int mid = (l + r) / 2;
	int res = find(v << 1 | 1, mid, r, val, suf);
	if (res == -1) res = find(v << 1, l, mid, val, suf);
	return res;
}

pii find2(int v, int l, int r, int ql, int qr, pll val){
	if (qr <= l || r <= ql) return {-1, 0};
	if (ql <= l && r <= qr && seg[v].F > val.F && seg[v].S < val.S) return {-1, 0};
	if (l + 1 == r){
		pii ret = {l, 0};
		if (seg[v].S == val.S) ret.S = 1;
		return ret;
	}
	shift(v, l, r);
	int mid = (l + r) / 2;
	pii res = find2(v << 1, l, mid, ql, qr, val);
	if (res.F == -1) res = find2(v << 1 | 1, mid, r, ql, qr, val);
	return res;
}

int get(int v, int l, int r, int idx){
	if (l + 1 == r) return seg[v].F;
	shift(v, l, r);
	int mid = (l + r) / 2;
	if (idx < mid) return get(v << 1, l, mid, idx);
	return get(v << 1 | 1, mid, r, idx);
}

void shift(int v, int l, int r){
	if (!lazy[v]) return;
	int mid = (l + r) / 2;
	add(v << 1, l, mid, l, mid, lazy[v]);
	add(v << 1 | 1, mid, r, mid, r, lazy[v]);
	lazy[v] = 0;
}

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V){
	n = C.size();
	q = L.size();
	for (int i = 0; i < n; i++){
		c[i] = C[i];
	}
	for (int i = 0; i < q; i++){
		Q[L[i]].push_back({i, V[i]});
		Q[R[i]+1].push_back({i, -V[i]});
	}
	add(1, -2, q, -2, -1, inf);
	vector<int> ans(n);
	for (int i = 0; i < n; i++){
		for (auto [x, y]: Q[i]){
	//		debug(x, y);
			add(1, -2, q, x, q, y);
		}
		pll tmp = {inf, -inf};
		int idx = find(1, -2, q, c[i], tmp);
	//	debug(i, idx, tmp.F, tmp.S);
		pii idx2 = find2(1, -2, q, idx+1, q, tmp);
	//	debug(idx2.F, idx2.S);
		ans[i] = get(1, -2, q, q) - get(1, -2, q, idx2.F);
	//	debug(ans[i]);
		if (idx2.S == 1) ans[i] += c[i];
	//	debug(ans[i]);
	}
	return ans;
}

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