Submission #1019590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019590		aufan	Distributing Candies (IOI21_candies)	C++17	0 / 100	125 ms	94036 KiB

candies

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

struct res {
    long long mn, mx;
};

struct node {
    res val;
    long long lz;
    int st, en;
    node *left, *right;

    res merge(res l, res r) {
        res ret;
        ret.mn = min(l.mn, r.mn);
        ret.mx = max(l.mx, r.mx);

        return ret;
    }

    void build(int start, int end) {
        st = start;
        en = end;

        if (st == en) {
            val.mn = val.mx = 0;
            return;
        }

        int md = (st + en) / 2;
        left = new node();
        right = new node();

        left->build(st, md);
        right->build(md + 1, en);

        val = merge(left->val, right->val);
    }

    void lazy() {
        left->val.mn += lz;
        left->val.mx += lz;
        left->lz += lz;

        right->val.mn += lz;
        right->val.mx += lz;
        right->lz += lz;

        lz = 0;
    }

    res query(int lf, int rg) {
        if (lf <= st && en <= rg) return val;
        lazy();
        if (rg <= left->en) return left->query(lf, rg);
        if (lf >= right->st) return left->query(lf, rg);
        return merge(left->query(lf, rg), right->query(lf, rg));
    }
    
    void update(int lf, int rg, int x) {
        if (st > rg || en < lf) return;
        if (lf <= st && en <= rg) {
            val.mn += x;
            val.mx += x;
            lz += x;
            return;
        }

        lazy();
        left->update(lf, rg, x);
        right->update(lf, rg, x);

        val = merge(left->val, right->val);
    }
} sg;
 
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size(), q = (int)l.size();
    vector<vector<pair<int, int>>> qr(n + 1);
    for (int i = 0; i < q; i++) {
        qr[l[i]].push_back({i + 1, v[i]});
        qr[r[i] + 1].push_back({i + 1, -v[i]});
    }

    vector<int> ans(n);
    sg.build(0, q);
    for (int i = 0; i < n; i++) {
        for (auto [j, x] : qr[i]) {
            sg.update(j, q, x);
        }

        auto [mn, mx] = sg.query(0, q);
        long long val = sg.query(q, q).mn;
        if (mx - mn <= c[i]) {
            ans[i] = val - mn;
            continue;
        }

        int lf = 0, rg = q, pos = -1;
        while (lf <= rg) {
            int md = (lf + rg) / 2;
            auto [cmn, cmx] = sg.query(md, q);

            if (cmx - cmn > c[i]) {
                pos = md;
                lf = md + 1;
            } else {
                rg = md - 1;
            }
        }

        long long nw = sg.query(pos, pos).mn;
        auto [fmn, fmx] = sg.query(pos, q);

        if (nw == fmn) {
            ans[i] = c[i] - (fmx - val);
        } else if (nw == fmx) {
            ans[i] = val - fmn;
        }
    }

    return ans;
}

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