Submission #593481

#	Time	Username	Problem	Language	Result	Execution time	Memory
593481		MadokaMagicaFan	Distributing Candies (IOI21_candies)	C++17	100 / 100	1404 ms	58912 KiB

candies

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
const ll inf = 1e17;
const int md1 = 1e9+7;
const int md2 = 998244353;

#define sz(v)                       ((int)v.size())
#define pb                          push_back

#define pry                         cout << "YES\n"
#define prn                         cout << "NO\n"
#define endl                        '\n'

#define fst                         first
#define scn                         second
/* #define ONPC */

using vi = vector<int>;
using vl = vector<long long>;
using pl = pair<ll,ll>;

struct aint{
    int n;
    vector<pl> mn, mx;
    vl lenes;
    vl sum;
    vi mid;

    aint(int _n)
        : n(_n)
    {
        mn.assign(4*n,{inf,0});
        mx.assign(4*n,{-inf,0});
        mid.assign(4*n, 0);
        sum.assign(4*n, 0);
        lenes.assign(4*n,0);

        build(1, 0, n-1);
    }

    void
    build(int i, int l, int r)
    {
        mid[i] = (l+r)>>1;
        mn[i].scn = r;
        mn[i].fst = 0;
        mx[i].scn = r;
        mx[i].fst = 0;

        if (l == r) return;

        build(i<<1, l, mid[i]);
        build(i<<1|1, mid[i]+1, r);
    }

    pl
    querymn(int i, int l, int r, int tl, int tr, ll ex)
    {
        ex += lenes[i];
        if (tr < l || r < tl) return {inf, 0};
        if (tl <= l && r <= tr) return {mn[i].fst+ex, mn[i].scn};

        auto lf = querymn(i<<1, l, mid[i], tl, tr, ex);
        auto rt = querymn(i<<1|1, mid[i]+1, r, tl, tr, ex);

        if (lf.fst < rt.fst) return lf;

        return rt;
    }

    pl
    querymx(int i, int l, int r, int tl, int tr, ll ex)
    {
        ex += lenes[i];
        if (tr < l || r < tl) return {-inf, 0};
        if (tl <= l && r <= tr) return {mx[i].fst+ex, mx[i].scn};

        auto lf = querymx(i<<1, l, mid[i], tl, tr, ex);
        auto rt = querymx(i<<1|1, mid[i]+1, r, tl, tr, ex);

        if (lf.fst > rt.fst) return lf;

        return rt;
    }

    void
    lenesupd(int i, int l, int r, int tl, int tr, int v)
    {
        if (tr < l || r < tl) return;
        if (tl <= l && r <= tr) {
            lenes[i] += v;
            return;
        }


        lenesupd(i<<1, l, mid[i], tl, tr, v);
        lenesupd(i<<1|1, mid[i]+1, r, tl, tr, v);

        int ind;

        if (mn[i<<1].fst+lenes[i<<1] < mn[i<<1|1].fst + lenes[i<<1|1]) 
            ind = i<<1;
        else
            ind = i<<1|1;

        mn[i] = {mn[ind].fst+lenes[ind], mn[ind].scn};

        if (mx[i<<1].fst+lenes[i<<1] > mx[i<<1|1].fst + lenes[i<<1|1]) 
            ind = i<<1;
        else
            ind = i<<1|1;
        mx[i] = {mx[ind].fst+lenes[ind], mx[ind].scn};
    }

    void
    updsum(int i, int l, int r, int x, int v)
    {
        if (x < l || r < x) return;

        sum[i] += v;
        if (l == r) return;

        updsum(i<<1, l, mid[i], x, v);
        updsum(i<<1|1, mid[i]+1, r, x, v);
    }

    void
    upd(int x, int v)
    {
        lenesupd(1, 0, n-1, x, n-1, v);
        updsum(1, 0, n-1, x, v);
        return;
    }

    ll
    qsum(int i, int l, int r, int tl, int tr)
    {
        if (tr < l || r < tl) return 0;
        if (tl <= l && r <= tr) return sum[i];

        return
            qsum(i<<1, l, mid[i], tl, tr) +
            qsum(i<<1|1, mid[i]+1, r, tl, tr);
    }

    /* User functions */
    pl querymn(int l, int r) { return querymn(1, 0, n-1, l, r, 0); }
    pl querymx(int l, int r) { return querymx(1, 0, n-1, l, r, 0); }
    ll qsum(int x) { return qsum(1, 0, n-1, x, n-1); }

    pl
    query(int x, int& ismx)
    {
        auto mx = querymx(x, n-1);
        auto mn = querymn(x, n-1);
        ismx = (mx.scn > mn.scn) ? 1 : 0;
        return {mx.fst - mn.fst, max(mx.scn, mn.scn)};
    }
};

vi
distribute_candies(vi c, vi l, vi r, vi v)
{
    int n = sz(c);
    int q = sz(l);
    vi ans;

    aint tr(q+1);

    vector<array<int,2>> qin, qout;

    for (int i = 0; i < q; ++i) {
        qin.pb({l[i],i});
        qout.pb({r[i],i});
    }

    sort(qin.begin(), qin.end());
    sort(qout.begin(), qout.end());

    int pin = 0;
    int pout = 0;

    for (int i = 0; i < n; ++i) {
        while (pout < q) {
            if (qout[pout][0] >= i) break;
            tr.upd(qout[pout][1]+1, -v[qout[pout][1]]);
            /* printf("i(%d) remove q(%d)\n", i, qout[pout][1]); */
            ++pout;
        }
        while (pin < q) {
            if (qin[pin][0] > i) break;
            tr.upd(qin[pin][1]+1, v[qin[pin][1]]);
            /* printf("i(%d) add q(%d)\n", i, qin[pin][1]); */
            ++pin;
        }

        /* Find valid */
        int sp = tr.querymn(0, q).scn;
        ll a;
        if (sp == q) {
            ans.pb(0);
            continue;
        }

        /* cout << sp << endl; */

        int ismx, tismx;
        ismx = 0;
        int sump = sp;

        int l, r, mid;
        l = sp;
        r = q+1;


        while (l < r) {
            int mid = (l+r)>>1;

            auto qr = tr.query(mid,tismx);
            if (qr.fst > c[i]) {
                l = mid+1;
                if (qr.scn > sump) {
                    sump = qr.scn;
                    ismx = tismx;
                }
            } else {
                r = mid;
            }
        }

        if (ismx)
            a = c[i];
        else
            a = 0;

        if (sump < q)
            a += tr.qsum(sump+1);

        a = max(a,0ll);
        a = min(a,(ll)c[i]);

        ans.pb(a);
    }


    return ans;
}

#ifdef ONPC
void
solve()
{
    int n, q;
    cin >> n >> q;

    vector<int> c(n);
    for (int i = 0; i < n; ++i)
        cin >> c[i];
    
    vector<int> l(q), r(q), v(q);
    for (int i = 0; i < q; ++i)
        cin >> l[i] >> r[i] >> v[i];

    vi ans = distribute_candies(c,l,r,v);

    for (int i = 0; i < sz(ans); ++i) {
        cout << ans[i] << ' ';
    }
    cout << endl;
}

int32_t
main(int argc, char **argv)
{
    if (argc >= 2) {
        freopen(argv[1], "r", stdin);
    } else
        ios_base::sync_with_stdio(0);cin.tie(0);
    int t = 1;
    /* cin >> t; */
    while(t--)
        solve();
}
#endif

Compilation message (stderr)

candies.cpp: In function 'vi distribute_candies(vi, vi, vi, vi)':
candies.cpp:214:19: warning: unused variable 'mid' [-Wunused-variable]
  214 |         int l, r, mid;
      |                   ^~~

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