Submission #441778

#	Time	Username	Problem	Language	Result	Execution time	Memory
441778		baluteshih	Distributing Candies (IOI21_candies)	C++17	29 / 100	349 ms	32440 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define pb push_back
#define ALL(v) v.begin(), v.end()
#define SZ(a) ((int)a.size())

struct node {
    ll lazy; // add
    ll mx, mi;
    node(ll _mx = 0, ll _mi = 0):lazy(0), mx(_mx), mi(_mi){}
    node operator+(const node &a)const {
        return node(max(mx, a.mx), min(mi, a.mi));
    }
} seg[800005];

vector<ll> seq;

void lazytag(int rt, ll lazy) {
    if (lazy != 0) {
        seg[rt].mx += lazy;
        seg[rt].mi += lazy;
        seg[rt].lazy += lazy;
    }
}

void down(int rt) {
    lazytag(rt << 1, seg[rt].lazy);
    lazytag(rt << 1 | 1, seg[rt].lazy);
    seg[rt].lazy = 0;
}

void modify(int L, int R, int l, int r, int rt, ll v) {
    if (L <= l && R >= r)
        return lazytag(rt, v);
    down(rt);
    int mid = (l + r) >> 1;
    if (L <= mid)
        modify(L, R, l, mid, rt << 1, v);
    if (R > mid)
        modify(L, R, mid + 1, r, rt << 1 | 1, v);
    seg[rt] = seg[rt << 1] + seg[rt << 1 | 1];
}

pll querybig(int x, int l, int r, int rt, ll c) {
    if (l == r)
        return pll(l, seg[rt].mx);
    down(rt);
    int mid = (l + r) >> 1;
    if (x <= mid && seg[rt << 1].mx > c) {
        pll r = querybig(x, l, mid, rt << 1, c);
        if (r.X != -1)
            return r;
    }
    if (seg[rt << 1 | 1].mx > c)
        return querybig(x, mid + 1, r, rt << 1 | 1, c);
    return pll(-1, 0);
}

pll querymin(int x, int l, int r, int rt, int c) {
    if (l == r) 
        return pll(l, seg[rt].mi);
    down(rt);
    int mid = (l + r) >> 1;
    if (x <= mid && seg[rt << 1].mi <= c) {
        pll r = querymin(x, l, mid, rt << 1, c);
        if (r.X != -1)
            return r;
    }
    if (seg[rt << 1 | 1].mi <= c)
        return querymin(x, mid + 1, r, rt << 1 | 1, c);
    return pll(-1, 0);
}

ll query(int l, int r, int rt) {
    if (l == r)
        return seg[rt].mi;
    down(rt);
    int mid = (l + r) >> 1;
    return query(mid + 1, r, rt << 1 | 1);
}

void build(int l, int r, int rt) {
    if (l == r)
        return seg[rt] = node(seq[l], seq[l]), void();
    int mid = (l + r) >> 1;
    build(l, mid, rt << 1), build(mid + 1, r, rt << 1 | 1);
    seg[rt] = seg[rt << 1] + seg[rt << 1 | 1];
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size();
    vector<int> rt(n, 0);
    vector<pii> arr(n);
    for (int i = 0; i < n; ++i)
        arr[i] = pii(c[i], i);
    sort(ALL(arr), greater<pii>());
    seq.pb(0);
    for (int i = 0; i < SZ(v); ++i)
        if (seq.back() + v[i] <= 0)
            seq.clear(), seq.pb(0);
        else
            seq.pb(seq.back() + v[i]);
    build(0, SZ(seq) - 1, 1);
    int tp = 1;
    for (int i = 0; i < n; ++i) {
        for (pll r; (r = querybig(tp, 0, SZ(seq) - 1, 1, arr[i].X)).X != -1;) {
            int beg = r.X;
            ll val = r.Y - arr[i].X;
            for (pll pl; beg + 1 < SZ(seq) && (pl = querymin(beg + 1, 0, SZ(seq) - 1, 1, val)).X != -1;) {
                beg = pl.X;
                val = pl.Y;
                tp = pl.X + 1;
                if (beg >= SZ(seq) - 1)
                    break;
            }
            //cerr << "modify " << beg << "-> " << -val << "\n";  
            modify(beg, SZ(seq) - 1, 0, SZ(seq) - 1, 1, -val);
            if (tp == SZ(seq))
                break;
        }
        if (tp == SZ(seq))
            break;
        rt[arr[i].Y] = query(0, SZ(seq) - 1, 1);
        //cerr << "fin " << arr[i].Y << " " << rt[arr[i].Y] << endl;
    }
    return rt;
}

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