Submission #1207690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207690		tkm_algorithms	Distributing Candies (IOI21_candies)	C++20	27 / 100	431 ms	15744 KiB

candies

/**
*    In the name of Allah
*    We are nothing and you're everything
**/
#include <bits/stdc++.h>
#include "candies.h" 
using namespace std;
using ll = long long;
using ull = uint64_t;
 
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
//#define int long long
 
const char nl = '\n';
const int N = 2e5+1;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const int mod = 1e9+7;
int C;

struct node {
	int set, mn, mx, lz;
	node() {
		set = -1, mn = 0, mx = 0, lz = 0;
	}
};

struct segtree {
	vector<node> tree;
	int size;
	
	void init(int n) {
		size = 1;
		while (size < n)size <<= 1;
		tree.assign(2*size-1, node());
	}
	
	void apply(int x, int v) {
		tree[x].mn = tree[x].mx = tree[x].set = v;
		tree[x].lz = 0;
	}
	
	void add(int x, int v) {
		tree[x].mn += v;
		tree[x].mx += v;
		tree[x].lz += v;
	}
	
	void push(int x, int y) {
		if (tree[x].set != -1) {
			apply(y, tree[x].set);
			tree[x].set = -1, tree[y].lz = 0;
		}
		if (tree[x].lz != 0) {
			add(y, tree[x].lz);
			tree[x].lz = 0;
		}
	}
	
	void radd(int l, int r, int v, int x, int lx, int rx) {
		if (rx <= l || r <= lx)return;
		if (lx >= l && rx <= r) {
			add(x, v);
			//cout << tree[x].mn << " " << tree[x].mx << " " << tree[x].set << " " << tree[x].lz << nl;
			return;
		}
		node a = tree[x];
		push(x, 2*x+1); tree[x] = a; push(x, 2*x+2);
		int mid = lx+rx>>1;
		radd(l, r, v, 2*x+1, lx, mid);
		radd(l, r, v, 2*x+2, mid, rx);
		tree[x].mn = min(tree[2*x+1].mn, tree[2*x+2].mn);
		tree[x].mx = max(tree[2*x+1].mx, tree[2*x+2].mx);
	}
	
	void radd(int l, int r, int v) {
		radd(l, r, v, 0, 0, size);
	}
	
	void minimize(int l, int r, int x, int lx, int rx) {
		if (rx <= l || r <= lx || tree[x].mx <= C)return;
		if (lx >= l && rx <= r)
			if (tree[x].mn > C) {
				apply(x, C);
				return;
			}
		node a = tree[x];
		push(x, 2*x+1); tree[x] = a; push(x, 2*x+2);
		int mid = lx+rx>>1;
		minimize(l, r, 2*x+1, lx, mid);
		minimize(l, r, 2*x+2, mid, rx);
		tree[x].mn = min(tree[2*x+1].mn, tree[2*x+2].mn);
		tree[x].mx = max(tree[2*x+1].mx, tree[2*x+2].mx);
	}
	
	void minimize(int l, int r) {
		minimize(l, r, 0, 0, size);
	}
	
	void maximize(int l, int r, int x, int lx, int rx) {
		if (rx <= l || r <= lx || tree[x].mn >= 0)return;
		if (lx >= l && rx <= r)
			if (tree[x].mx < 0) {
				apply(x, 0);
				return;
			}
		node a = tree[x];
		push(x, 2*x+1); tree[x] = a; push(x, 2*x+2);
		int mid = lx+rx>>1;
		maximize(l, r, 2*x+1, lx, mid);
		maximize(l, r, 2*x+2, mid, rx);
		tree[x].mn = min(tree[2*x+1].mn, tree[2*x+2].mn);
		tree[x].mx = max(tree[2*x+1].mx, tree[2*x+2].mx);
	}
	
	void maximize(int l, int r) {
		maximize(l, r, 0, 0, size);
	}
	
	int get(int i, int x, int lx, int rx) {
		if (rx-lx==1) {
			//cout << tree[x].mn << nl;
			assert(tree[x].mn == tree[x].mx);
			return tree[x].mn;
		}
		int mid = lx+rx>>1;
		node a = tree[x];
		push(x, 2*x+1); tree[x] = a; push(x, 2*x+2);
		if (i < mid)return get(i, 2*x+1, lx, mid);
		else return get(i, 2*x+2, mid, rx);
		tree[x].mn = min(tree[2*x+1].mn, tree[2*x+2].mn);
		tree[x].mx = max(tree[2*x+1].mx, tree[2*x+2].mx);
	}
	
	int get(int i) {
		return get(i, 0, 0, size);
	}	
};

vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> v) {
	int n = sz(c), q = sz(l);
    C = c[0];
    
    segtree st; st.init(n+1);
    for (int i = 0; i < q; ++i) {
		st.radd(l[i], r[i]+1, v[i]);
		if (v[i] > 0)st.minimize(l[i], r[i]+1);
		if (v[i] < 0)st.maximize(l[i], r[i]+1);
	}
	
	vector<int> res(n);
	for (int i = 0; i < n; ++i)res[i] = st.get(i);
	return res;
}

//int main() {
	//vector<int> ans = distribute_candies({15, 15, 15}, {0, 0}, {1, 2}, {10, 100});
	//for (auto &i: ans)cout << i << " ";
	//return 0;
//}

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