Submission #441839

#	Time	Username	Problem	Language	Result	Execution time	Memory
441839		baluteshih	Distributing Candies (IOI21_candies)	C++17	27 / 100	1174 ms	55424 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())

const ll INF = 1e18;
struct node {
    ll lazymax, lazymin, lazyadd;
    ll mx, smx;
    ll mi, smi;
    node(ll d = 0):lazymax(-INF), lazymin(INF), lazyadd(0), mx(d), smx(-INF), mi(d), smi(INF){}
    node operator+(const node &a) const {
        node rt;
        rt.mx = max(mx, a.mx);
        rt.mi = min(mi, a.mi);
        if (mx == a.mx)
            rt.smx = max(smx, a.smx);
        else if (mx > a.mx)
            rt.smx = max(smx, a.mx);
        else
            rt.smx = max(mx, a.smx);
        if (mi == a.mi)
            rt.smi = min(smi, a.smi);
        else if (mi < a.mi)
            rt.smi = min(smi, a.mi);
        else
            rt.smi = min(mi, a.smi);
        rt.lazymax = -INF;
        rt.lazymin = INF;
        rt.lazyadd = 0;
        return rt;
    }
} seg[800005];

void give_tag_min(int rt, ll t) {
    if (t >= seg[rt].mx) return;
    seg[rt].lazymin = t;
    seg[rt].lazymax = min(seg[rt].lazymax, t);
    if (seg[rt].mx == seg[rt].smi)
        seg[rt].smi = t;
    if (seg[rt].mx == seg[rt].mi)
        seg[rt].mi = t;
    seg[rt].mx = t;
}

void give_tag_max(int rt, ll t) {
    if (t <= seg[rt].mi) return;
    seg[rt].lazymax = t;
    seg[rt].lazymin = max(seg[rt].lazymin, t);
    if (seg[rt].mi == seg[rt].smx)
        seg[rt].smx = t;
    if (seg[rt].mi == seg[rt].mx)
        seg[rt].mx = t;
    seg[rt].mi = t;
}

void give_tag_add(int rt, ll t) {
    seg[rt].lazyadd += t;
    if (seg[rt].lazymax != -INF)
        seg[rt].lazymax += t;
    if (seg[rt].lazymin != INF)
        seg[rt].lazymin += t;
    seg[rt].mx += t;
    if (seg[rt].smx != -INF)
        seg[rt].smx += t;
    seg[rt].mi += t;
    if (seg[rt].smi != INF)
        seg[rt].smi += t;
}

void down(int rt) {
    if (seg[rt].lazyadd != 0) {
        give_tag_add(rt << 1, seg[rt].lazyadd);
        give_tag_add(rt << 1 | 1, seg[rt].lazyadd);
        seg[rt].lazyadd = 0;
    }
    if (seg[rt].lazymin != INF) {
        give_tag_min(rt << 1, seg[rt].lazymin);
        give_tag_min(rt << 1 | 1, seg[rt].lazymin);
        seg[rt].lazymin = INF;
    }
    if (seg[rt].lazymax != -INF) {
        give_tag_max(rt << 1, seg[rt].lazymax);
        give_tag_max(rt << 1 | 1, seg[rt].lazymax);
        seg[rt].lazymax = -INF;
    }
}

void modifymx(int l, int r, int rt, ll t) {
    if (t < seg[rt].smi)
        return give_tag_max(rt, t);
    if (l != r) down(rt);
    int mid = (l + r) >> 1;
    modifymx(l, mid, rt << 1, t);
    modifymx(mid + 1, r, rt << 1 | 1, t);
    seg[rt] = seg[rt << 1] + seg[rt << 1 | 1];
}

void modifymi(int l, int r, int rt, ll t) {
    if (t > seg[rt].smx)
        return give_tag_min(rt, t);
    if (l != r) down(rt);
    int mid = (l + r) >> 1;
    modifymi(l, mid, rt << 1, t);
    modifymi(mid + 1, r, rt << 1 | 1, t);
    seg[rt] = seg[rt << 1] + seg[rt << 1 | 1];
}

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

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

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size();
    vector<int> ans(n);
    for (int i = 0; i < SZ(l); ++i) {
        modifyadd(l[i], r[i], 0, n - 1, 1, v[i]);
        modifymx(0, n - 1, 1, 0);
        modifymi(0, n - 1, 1, c[0]);
    }
    query(0, n - 1, 1, ans);
    return ans;
}

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