Submission #1043529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043529		AmirAli_H1	Distributing Candies (IOI21_candies)	C++17	11 / 100	272 ms	62292 KiB

candies

// In the name of Allah

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

typedef		__int128				ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;

#define		endl					'\n'
#define		sep						' '
#define		F						first
#define		S						second
#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		pb						push_back
#define		Mp						make_pair

const int maxn = 2e5 + 4;
const ll oo = 1e18 + 4;

struct node {
	ll val;
	pll lazym; ll lazys;
};

int n, q;
int A[maxn]; pair<pii, int> Q[maxn];
int val[maxn]; vector<int> ans;
node t[4 * maxn];

void solve1() {
	for (int i = 0; i < q; i++) {
		int l = Q[i].F.F, r = Q[i].F.S, x = Q[i].S;
		for (int j = l; j < r; j++) {
			val[j] += x;
			val[j] = (val[j] >= 0) ? val[j] : 0;
			val[j] = (val[j] <= A[j]) ? val[j] : A[j];
		}
	}
}

void shift(int v, int tl, int tr) {
	ll x1 = t[v].lazym.F, x2 = t[v].lazym.S, R = t[v].lazys;
	t[v].lazym = Mp(oo, -oo); t[v].lazys = 0;
	if (tr - tl == 1) return ;
	
	for (int u : {2 * v + 1, 2 * v + 2}) {
		t[u].val = min(t[u].val, x1); t[u].val = max(t[u].val, x2);
		t[u].val += R;
		
		t[u].lazym.F = min(t[u].lazym.F, x1 - t[u].lazys);
		t[u].lazym.S = max(t[u].lazym.S, x2 - t[u].lazys);
		if (t[u].lazym.S > t[u].lazym.F) t[u].lazym.F = t[u].lazym.S;
		t[u].lazys += R;
	}
}

void build(int v, int tl, int tr) {
	t[v].val = 0;
	t[v].lazym = Mp(oo, -oo); t[v].lazys = 0;
	if (tr - tl == 1) return ;
	int mid = (tl + tr) / 2;
	build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
}

void add_val(int v, int tl, int tr, int l, int r, ll x) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl) return ;
	shift(v, tl, tr);
	if (l == tl && r == tr) {
		t[v].val += x; t[v].lazys += x;
		return ;
	}
	int mid = (tl + tr) / 2;
	add_val(2 * v + 1, tl, mid, l, r, x); add_val(2 * v + 2, mid, tr, l, r, x);
}

void set_min(int v, int tl, int tr, int l, int r, ll x) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl) return ;
	shift(v, tl, tr);
	if (l == tl && r == tr) {
		t[v].val = min(t[v].val, x);
		t[v].lazym.F = min(t[v].lazym.F, x);
		if (t[v].lazym.S > t[v].lazym.F) t[v].lazym.F = t[v].lazym.S;
		return ;
	}
	int mid = (tl + tr) / 2;
	set_min(2 * v + 1, tl, mid, l, r, x); set_min(2 * v + 2, mid, tr, l, r, x);
}

void set_max(int v, int tl, int tr, int l, int r, ll x) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl) return ;
	shift(v, tl, tr);
	if (l == tl && r == tr) {
		t[v].val = max(t[v].val, x);
		t[v].lazym.S = max(t[v].lazym.S, x);
		if (t[v].lazym.S > t[v].lazym.F) t[v].lazym.F = t[v].lazym.S;
		return ;
	}
	int mid = (tl + tr) / 2;
	set_max(2 * v + 1, tl, mid, l, r, x); set_max(2 * v + 2, mid, tr, l, r, x);
}

void get_res(int v, int tl, int tr) {
	shift(v, tl, tr);
	if (tr - tl == 1) {
		val[tl] = max((ll) 0, min((ll) A[tl], (ll) t[v].val));
		return ;
	}
	int mid = (tl + tr) / 2;
	get_res(2 * v + 1, tl, mid); get_res(2 * v + 2, mid, tr);
}

void solve2() {
	int mx = *max_element(A, A + n);
	build(0, 0, n);
	for (int i = 0; i < q; i++) {
		int l = Q[i].F.F, r = Q[i].F.S, x = Q[i].S;
		add_val(0, 0, n, l, r, x);
		if (x < 0) set_max(0, 0, n, 0, n, 0);
		else set_min(0, 0, n, 0, n, mx);
	}
	get_res(0, 0, n);
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	n = len(c); q = len(l);
	for (int i = 0; i < n; i++) A[i] = c[i];
	for (int i = 0; i < q; i++) Q[i] = Mp(Mp(l[i], r[i] + 1), v[i]);
	fill(val, val + n, 0);
	
	if (n <= 2000 && q <= 2000) solve1();
	else solve2();
	
	ans.clear(); ans.resize(n);
	for (int i = 0; i < n; i++) ans[i] = val[i];
	return ans;
}

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