Submission #1127208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127208		Wendidiask	Distributing Candies (IOI21_candies)	C++20	29 / 100	430 ms	49900 KiB

candies

// Hello this is Tyx2019's clone
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define debug(x) cerr << #x << " is " << x << "\n"
#define hehe ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repb(i, a, b) for (int i = b; i >= a; i--)
#define pii pair<int, int>
#define linebreak cout << "---------------------------------------------------------\n"
#define f first
#define s second
#define pb push_back
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// good luck
const long long MS = 2e5+5, mod = 1e9+9, INF = 3e18, blk = 400;
long long n, q;
struct node {
	long long S, E;
	long long lazy = 0, macs = 0, ming = 0;
	node *left = NULL, *right = NULL;
	node (long long s, long long e) {
		S = s;
		E = e;
		macs = ming = 0;
	}
	void create() {
		long long M = (S+E)>>1;
		if (S != E) {
			left = new node(S, M);
			right = new node(M+1, E);
		}
	}
	void propagate() {
		if (left == NULL or right == NULL) create();
		if (lazy == 0) return;
		macs += lazy; ming += lazy;
		if (S != E) {
			left -> lazy += lazy;
			right -> lazy += lazy;
		}
		lazy = 0;
	}
	void update(long long us, long long ue, long long v) {
		long long M = (S+E)>>1;
		propagate();
		if (S == us and E == ue) {
			lazy += v;
			return;
		}
		if (ue <= M) left -> update(us, ue, v);
		else if (us >= M+1) right -> update(us, ue, v);	
		else {
			left -> update(us, M, v);
			right -> update(M+1, ue, v);
		}
		left -> propagate();
		right -> propagate();
		macs = max(left -> macs, right -> macs);
		ming = min(left -> ming, right -> ming);
	}	
	pair<long long, pair<long long, long long>> bs(long long x, long long omacs, long long oming) {
		if (S == E) return {S, {omacs, oming}};
		propagate();
		long long nmacs = max(omacs, right -> macs), nming = min(oming, right -> ming);
		if (nmacs-nming <= x) {
			return left -> bs(x, nmacs, nming);
		}
		else {
			return right -> bs(x, omacs, oming);
		}
	}
	long long query(long long x) {
		if (S == E) return ming;
		long long M = (S+E)>>1;
		propagate();
		if (x <= M) return left -> query(x);
		return right -> query(x);
	}
} *root;
vector<long long> L[MS], R[MS];
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	vector<int> ans;
	n = c.size(), q = v.size();
	for (long long i = 0; i < q; i++) {
		L[l[i]].pb(i); R[r[i]].pb(i);
	}
	root = new node(-2, q-1);
	root -> update(-2, -2, INF);
	for (long long i = 0; i < n; i++) {
		for (auto it : L[i]) root -> update(it, q-1, v[it]);
		long long endval = root -> query(q-1);
		// process query for i
		pair<long long, pair<long long, long long>> temp = root -> bs(c[i], -INF, INF);
		if (root -> query(temp.f) > temp.s.f) ans.pb(endval-temp.s.s);
		else ans.pb(c[i]-temp.s.f+endval);
		for (auto it : R[i]) root -> update(it, q-1, -v[it]);
	}
	return ans;
}

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