제출 #815412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
815412		becaido	사탕 분배 (IOI21_candies)	C++17	100 / 100	508 ms	38076 KiB

candies

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "candies.h"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

#define lpos pos*2
#define rpos pos*2+1

const ll INF = 1e18;
const int SIZE = 2e5 + 5;

int n, q;
vector<pair<int, int>> op[SIZE];

struct Node {
    ll mn, mx, lazy;
    Node() = default;
    Node operator + (const Node& r) const {
        Node re = Node();
        re.mn = min(mn, r.mn);
        re.mx = max(mx, r.mx);
        return re;
    }
} node[SIZE * 4];

void push(int pos, int l, int r) {
    node[pos].mn += node[pos].lazy;
    node[pos].mx += node[pos].lazy;
    if (l < r) {
        node[lpos].lazy += node[pos].lazy;
        node[rpos].lazy += node[pos].lazy;
    }
    node[pos].lazy = 0;
}
void pull(int pos, int l, int r) {
    int mid = (l + r) / 2;
    push(lpos, l, mid);
    push(rpos, mid + 1, r);
    node[pos] = node[lpos] + node[rpos];
}

void upd(int pos, int l, int r, int L, int R, int x) {
    if (l == L && r == R) {
        node[pos].lazy += x;
        return;
    }
    push(pos, L, R);
    int mid = (L + R) / 2;
    if (r <= mid) upd(lpos, l, r, L, mid, x);
    else if (l > mid) upd(rpos, l, r, mid + 1, R, x);
    else {
        upd(lpos, l, mid, L, mid, x);
        upd(rpos, mid + 1, r, mid + 1, R, x);
    }
    pull(pos, L, R);
}
void upd(int p, int x) {
    upd(1, p, q, 0, q, x);
}

ll que(int pos, int l, int r, int p) {
    push(pos, l, r);
    if (l == r) return node[pos].mn;
    int mid = (l + r) / 2;
    if (p <= mid) return que(lpos, l, mid, p);
    else return que(rpos, mid + 1, r, p);
}
ll que(int l, int r) {
    return que(1, 0, q, r) - (l ? que(1, 0, q, l - 1) : 0);
}
ll que(int pos, int l, int r, int L, int R, int ty) {
    push(pos, L, R);
    if (l == L && r == R) return (ty == 0 ? node[pos].mn : node[pos].mx);
    int mid = (L + R) / 2;
    if (r <= mid) return que(lpos, l, r, L, mid, ty);
    if (l > mid) return que(rpos, l, r, mid + 1, R, ty);
    ll lval = que(lpos, l, mid, L, mid, ty);
    ll rval = que(rpos, mid + 1, r, mid + 1, R, ty);
    return ty == 0 ? min(lval, rval) : max(lval, rval);
}

int sch_mn(int pos, int l, int r) {
    if (l == r) return l;
    int mid = (l + r) / 2;
    push(pos, l, r);
    push(rpos, mid + 1, r);
    if (node[rpos].mn == node[pos].mn) return sch_mn(rpos, mid + 1, r);
    else return sch_mn(lpos, l, mid);
}
int sch_mn() {
    return sch_mn(1, 0, q);
}

tuple<int, ll, ll> sch_rdif(int pos, int l, int r, int lim, ll pmn = INF, ll pmx = -INF) {
    push(pos, l, r);
    if (l == r) {
        pmn = min(pmn, node[pos].mn);
        pmx = max(pmx, node[pos].mx);
        return {l, pmn, pmx};
    }
    int mid = (l + r) / 2;
    push(rpos, mid + 1, r);
    ll rmn = min(pmn, node[rpos].mn);
    ll rmx = max(pmx, node[rpos].mx);
    if (rmx - rmn >= lim) return sch_rdif(rpos, mid + 1, r, lim, pmn, pmx);
    else return sch_rdif(lpos, l, mid, lim, rmn, rmx);
}
pair<int, int> sch_rdif(int lim) {
    auto [lp, mn, mx] = sch_rdif(1, 0, q, lim);
    return {lp, que(0, lp) != mn};
}

int sch(int pos, int l, int r, int L, int R, int ty, ll x, ll pval) {
    push(pos, L, R);
    if (l == L && r == R) {
        if (l == r) return l;
        int mid = (L + R) / 2;
        push(rpos, mid + 1, R);
        ll rval = (ty == 0 ? min(node[rpos].mn, pval) : max(node[rpos].mx, pval));
        if (rval == x) return sch(rpos, mid + 1, r, mid + 1, R, ty, x, pval);
        else return sch(lpos, l, mid, L, mid, ty, x, rval);
    }
    int mid = (L + R) / 2;
    if (l > mid) return sch(rpos, l, r, mid + 1, R, ty, x, pval);
    push(rpos, mid + 1, R);
    ll rval = (ty == 0 ? min(node[rpos].mn, pval) : max(node[rpos].mx, pval));
    if (rval == x) return sch(rpos, mid + 1, r, mid + 1, R, ty, x, pval);
    else return sch(lpos, l, mid, L, mid, ty, x, rval);
}
int sch(int l, int r, int ty) {
    ll x = que(1, l, r, 0, q, ty);
    return sch(1, l, r, 0, q, ty, x, (ty == 0 ? INF : -INF));
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    n = c.size(), q = l.size();
    FOR (i, 0, q - 1) {
        op[l[i]].pb(i + 1, v[i]);
        op[r[i] + 1].pb(i + 1, -v[i]);
    }
    vector<int> ans(n);
    FOR (i, 0, n - 1) {
        // debug(i);
        for (auto [p, x] : op[i]) {
            // debug("upd", p, x);
            upd(p, x);
        }
        if (node[1].mx - node[1].mn <= c[i]) {
            // debug("sch_mn");
            int lp = sch_mn();
            ans[i] = que(lp + 1, q);
            continue;
        }
        // debug("sch_rdif");
        auto [lp, ty] = sch_rdif(c[i]);
        // debug("sch", lp, ty);
        int rp = sch(lp + 1, q, !ty);
        ans[i] = (ty == 0 ? c[i] : 0) + que(rp + 1, q);
    }
    return ans;
}

/*
in1
3
10 15 13
2
0 2 20
0 1 -11
out1
0 4 13
*/

#ifdef WAIMAI
int main() {
    int n;
    assert(1 == scanf("%d", &n));
    vector<int> c(n);
    for(int i = 0; i < n; ++i) {
        assert(scanf("%d", &c[i]) == 1);
    }

    int q;
    assert(1 == scanf("%d", &q));
    vector<int> l(q), r(q), v(q);
    for(int i = 0; i < q; ++i) {
        assert(scanf("%d %d %d", &l[i], &r[i], &v[i]) == 3);
    }

    vector<int> ans = distribute_candies(c, l, r, v);

    for(int i = 0; i < n; ++i) {
        if (i > 0) {
            printf(" ");
        }
        printf("%d", ans[i]);
    }
    printf("\n");
    fclose(stdout);
    return 0;
}
#endif

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