Submission #1242484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242484		k1r1t0	Distributing Candies (IOI21_candies)	C++20	100 / 100	374 ms	51048 KiB

candies

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll INF = (ll)(1e18);
const int N = 210000;

int n, q;

struct segtree {
	struct node {
		ll mn, mnpos, mx, mxpos, lz;
		node() {mn = INF; mx = -INF;}
	};
	vector<node> vv;
	int n;
	segtree(int n) {
		this->n = n;
		vv = vector<node>(4 * (n + 1) + 1);
		build(1, 0, n);
	}
	void build(int v, int l, int r) {
		vv[v].mn = vv[v].mx = vv[v].lz = 0;
		vv[v].mnpos = vv[v].mxpos = r;
		if (l == r) return;
		int mid = (l + r) / 2;
		build(v * 2 + 0, l, mid);
		build(v * 2 + 1, mid + 1, r);
	}
	void push(int v, int l, int r) {
		if (vv[v].lz == 0) return;
		vv[v].mn += vv[v].lz;
		vv[v].mx += vv[v].lz;
		if (l != r) {
			vv[v * 2 + 0].lz += vv[v].lz;
			vv[v * 2 + 1].lz += vv[v].lz;
		}
		vv[v].lz = 0;
	}
	node merge(node a, node b) {
		node res;
		res.mn = min(a.mn, b.mn);
		res.mx = max(a.mx, b.mx);
		if (b.mn <= a.mn) res.mnpos = b.mnpos;
		else res.mnpos = a.mnpos;
		if (b.mx >= a.mx) res.mxpos = b.mxpos;
		else res.mxpos = a.mxpos;
		return res;
	}
	void add(int v, int l, int r, int ql, int qr, int k) {
		push(v, l, r);
		if (qr < l || r < ql) return;
		if (ql <= l && r <= qr) {
			vv[v].lz += k;
			push(v, l, r);
			return;
		}
		int mid = (l + r) / 2;
		add(v * 2 + 0, l, mid, ql, qr, k);
		add(v * 2 + 1, mid + 1, r, ql, qr, k);
		vv[v] = merge(vv[v * 2 + 0], vv[v * 2 + 1]);
	}
	node getnode(int v, int l, int r, int ql, int qr) {
		push(v, l, r);
		if (qr < l || r < ql) return node();
		if (ql <= l && r <= qr) return vv[v];
		int mid = (l + r) / 2;
		return merge(getnode(v * 2 + 0, l, mid, ql, qr), getnode(v * 2 + 1, mid + 1, r, ql, qr));
	}
	ll getval(int v, int l, int r, int k) {
		push(v, l, r);
		if (l == r) return vv[v].mn;
		int mid = (l + r) / 2;
		if (k <= mid)
			return getval(v * 2 + 0, l, mid, k);
		return getval(v * 2 + 1, mid + 1, r, k);
	}
	ll smx, smn;
	int getpos(int v, int l, int r, int c) {
		push(v, l, r);
		ll cmx = max(vv[v].mx, smx);
		ll cmn = min(vv[v].mn, smn);
		if (cmx - cmn <= c) {
			smx = cmx;
			smn = cmn;
			return -1;
		}
		if (l == r) return l;
		int mid = (l + r) / 2;
		int ans = getpos(v * 2 + 1, mid + 1, r, c);
		if (ans != -1) return ans;
		return getpos(v * 2 + 0, l, mid, c);
	}
	void add(int ql, int qr, int k) {
		add(1, 0, n, ql, qr, k);
	}
	int getmin(int l, int r) {
		node tt = getnode(1, 0, n, l, r);
		return tt.mnpos;
	}
	int getmax(int l, int r) {
		node tt = getnode(1, 0, n, l, r);
		return tt.mxpos;
	}
	ll getval(int k) {
		return getval(1, 0, n, k);
	}
	int getpos(int c) {
		smx = -INF;
		smn = INF;
		return getpos(1, 0, n, c);
	}
};

vector<array<int, 2>> vv[N];

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 < q; i++) {
		l[i]++; r[i]++;
		vv[l[i]].push_back({i + 1, v[i]});
		vv[r[i] + 1].push_back({i + 1, -v[i]});
	}
	segtree seg(q);
	vector<int> ans;
	for (int i = 1; i <= n; i++) {
		for (auto [k, v] : vv[i])
			seg.add(k, q, v);
		int C = c[i - 1];
		int pos = seg.getpos(C);
		if (pos == -1) {
			int k = seg.getmin(0, q);
			ans.push_back(seg.getval(q) - seg.getval(k));
		} else {
			int mn = seg.getmin(pos, q);
			int mx = seg.getmax(pos, q);
			if (mn > mx)
				ans.push_back(seg.getval(q) - seg.getval(mn));
			else
				ans.push_back(seg.getval(q) - seg.getval(mx) + C);
		}
	}
	return ans;
}










/*
int main() {
    int n;
    assert(1 == scanf("%d", &n));
    std::vector<int> c(n);
    for(int i = 0; i < n; ++i) {
        assert(scanf("%d", &c[i]) == 1);
    }

    int q;
    assert(1 == scanf("%d", &q));
    std::vector<int> l(q), r(q), v(q);
    for(int i = 0; i < q; ++i) {
        assert(scanf("%d %d %d", &l[i], &r[i], &v[i]) == 3);
    }

    std::vector<int> ans = distribute_candies(c, l, r, v);

    for(int i = 0; i < n; ++i) {
        if (i > 0) {
            printf(" ");
        }
        printf("%d", ans[i]);
    }
    printf("\n");
    fclose(stdout);
    return 0;
}
//*/

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