Submission #1208200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208200		tkm_algorithms	Distributing Candies (IOI21_candies)	C++20	0 / 100	698 ms	39496 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 = int64_t;
 
#define all(x) begin(x), end(x)
#define sz(x) (ll)(x).size()
//#define ll long long
 
const char nl = '\n';
const ll N = 2e5+1;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const ll mod = 1e9+7;

struct node {
	ll mx, mn, mni, mxi, lz;
	node () {
		mx = -inf, mn = inf, mni = 0, mxi = 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 build(int x, int lx, int rx) {
		tree[x].mx = tree[x].mn = 0;
		tree[x].mni = tree[x].mxi = lx;
		tree[x].lz = 0;
		
		if (rx-lx==1)return;
		int mid = lx+rx>>1;
		build(2*x+1, lx, mid);
		build(2*x+2, mid, rx);
	}
	
	void build(int n) {
		init(n);
		build(0, 0, size);
	}
	
	void addval(int x, int v) {
		tree[x].mn += v, tree[x].mx += v;
		tree[x].lz += v;
	}
	
	void push(int x) {
		tree[2*x+1].mn += tree[x].lz;
		tree[2*x+2].mx += tree[x].lz;
		tree[2*x+1].lz += tree[x].lz;
		tree[2*x+2].lz += tree[x].lz;
		tree[x].lz = 0;
	}
	
	node comb(node a, node b) {
		node c;
		if (a.mx > b.mx)c.mx = a.mx, c.mxi = a.mxi;
		else c.mx = b.mx, c.mxi = b.mxi;
		if (a.mn < b.mn)c.mn = a.mn, c.mni = a.mni;
		else c.mn = b.mn, c.mni = b.mni;
		return c;
	}
	
	void add(int l, int r, int v, int x, int lx, int rx) {
		if (rx <= l || r <= lx)return;
		if (lx >= l && rx <= r) {
			addval(x, v);
			return;
		}
		push(x);
		int mid = lx+rx>>1;
		add(l, r, v, 2*x+1, lx, mid);
		add(l, r, v, 2*x+2, mid, rx);
		tree[x] = comb(tree[2*x+1], tree[2*x+2]);
	}
	
	void add(int l, int r, int v) {
		add(l, r, v, 0, 0, size);
	}
	
	node get(int l, int r, int x, int lx, int rx) {
		if (rx <= l || r <= lx)return node();
		if (lx >= l && rx <= r)return tree[x];
		int mid = lx+rx>>1;
		return comb(get(l, r, 2*x+1, lx, mid), get(l, r, 2*x+2, mid, rx));
	}
	
	node get(int l, int r) {
		return get(l, r, 0, 0, size);
	}
};

vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> v) {
    segtree st; st.build(sz(l)+1);
    int n = sz(c), q = sz(l);
    vector<pair<int, int>> g[n+1];
    for (int i = 0; i < q; ++i) {
		g[l[i]].push_back(make_pair(i, v[i]));
		if (r[i] < n-1)g[r[i]+1].push_back(make_pair(i, -v[i]));
	}
	
	vector<int> res(n);
	
	int sum = 0;
	for (int i = 0; i < n; ++i) {
		for (auto j: g[i]) {
			st.add(j.first, q, j.second);
			sum += j.second;
		}
		ll id = -1, wall = -1, tp = 0;
		int lx = 0, rx = q-1;
		while (lx <= rx) {
			int mid = lx+rx>>1;
			node gt = st.get(mid, q);
			if (gt.mx-gt.mn >= c[i]) {
				lx = mid+1;
				if (gt.mni < gt.mxi)id = gt.mni, wall = gt.mn;
				else id = gt.mxi, wall = gt.mx, tp = 1;
			} else rx = mid-1;
		}
		
		//cout << sum << nl;
		
		if (id == -1) {
			node gt = st.get(0, q);
			cout << gt.mn << " " << gt.mx << nl;
			if (gt.mn < 0)wall = gt.mn;
			if (gt.mx > 0 && gt.mx >= c[i])wall = gt.mx-c[i];
			res[i] = sum-wall;
			continue;
		}
		
		
		res[i] = (tp==0?sum-wall:sum-wall+c[i]);
	}
	return res;
}

void solve() {

	int n, q;
	cin >> n >> q;
	vector<int> c(n), l(q), r(q), v(q);
	for (auto &i : c) cin >> i;
	for (auto &i : l) cin >> i;
	for (auto &i : r) cin >> i;
	for (auto &i : v) cin >> i;
	vector<int> result = distribute_candies(c, l, r, v);
	for (const auto &i : result) cout << i << " "; 

	//int n;
	//cin >> n;
	//segtree T(n);
	//while (1) {
		//string op;
		//int l, r, v;
		//cin >> op;
		//if (op == "add") {
			//cin >> l >> v;
			//T.add(l, v);
		//}
		//else if (op == "minimix") {
			//cin >> l >> r;
			//info res = T.minimix(l, r);
			//printf("(%lld, %d), (%lld, %d)\n", res.mn, res.imn, res.mx, res.imx);
		//}
		//else if (op == "suffix") {
			//cin >> v;
			//info res = T.suffix(v);
			//printf("(%lld, %d), (%lld, %d)\n", res.mn, res.imn, res.mx, res.imx);
		//}
	//}
}
//int main() {
	//ios::sync_with_stdio(0), cin.tie(0);
	//solve();
//}

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