Submission #1025768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025768		thinknoexit	Distributing Candies (IOI21_candies)	C++17	100 / 100	675 ms	44732 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200200;
int n;
struct A {
    ll mn, mx;
    A() {
        mn = mx = 0ll;
    }
    A operator + (const A& o) const {
        A t;
        t.mn = min(mn, o.mn);
        t.mx = max(mx, o.mx);
        return t;
    }
} tree[4 * N], _T;
ll lazy[4 * N];
void lzy(int now, int l, int r) {
    if (!lazy[now]) return;
    tree[now].mn += lazy[now];
    tree[now].mx += lazy[now];
    if (l != r) {
        lazy[2 * now] += lazy[now];
        lazy[2 * now + 1] += lazy[now];
    }
    lazy[now] = 0;
}
void update(int ql, int qr, ll w, int now = 1, int l = 0, int r = n) {
    lzy(now, l, r);
    if (l > qr || r < ql) return;
    if (ql <= l && r <= qr) {
        lazy[now] += w;
        lzy(now, l, r);
        return;
    }
    int mid = (l + r) / 2;
    update(ql, qr, w, 2 * now, l, mid);
    update(ql, qr, w, 2 * now + 1, mid + 1, r);
    tree[now] = tree[2 * now] + tree[2 * now + 1];
}
A query(int ql, int qr, int now = 1, int l = 0, int r = n) {
    lzy(now, l, r);
    if (ql <= l && r <= qr) return tree[now];
    int mid = (l + r) / 2;
    if (qr <= mid) return query(ql, qr, 2 * now, l, mid);
    if (ql > mid) return query(ql, qr, 2 * now + 1, mid + 1, r);
    return query(ql, qr, 2 * now, l, mid) + query(ql, qr, 2 * now + 1, mid + 1, r);
}
vector<pair<int, int>> q[N];
vector<int> distribute_candies(vector<int> c, vector<int> _l, vector<int> _r, vector<int> _v) {
    n = _l.size();
    int m = c.size();
    vector<int> ans(m);
    for (int i = 0;i < n;i++) {
        q[_l[i]].push_back({ _v[i], i + 1 });
        q[_r[i] + 1].push_back({ -_v[i], i + 1 });
    }
    // find last point that mx - mn <= c[i]
    ll sum = 0;
    for (int i = 0;i < m;i++) {
        for (auto& x : q[i]) {
            update(x.second, n, x.first);
            sum += x.first;
        }
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r) / 2;
            A now = query(mid, n);
            if (now.mx - now.mn <= c[i]) r = mid;
            else l = mid + 1;
        }
        if (l == 0) {
            ans[i] = sum - query(0, n).mn;
            continue;
        }
        A now = query(l, n);
        ll prev = query(l - 1, l - 1).mn;
        if (prev < now.mn) {
            ans[i] = sum - (now.mx - c[i]);
        }
        else {
            ans[i] = sum - now.mn;
        }
    }
    return ans;
}

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