제출 #814367

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
814367		becaido	사탕 분배 (IOI21_candies)	C++17	8 / 100	349 ms	32092 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 sum, mx, mn;
    Node() = default;
    Node operator + (const Node& r) const {
        Node re;
        re.sum = sum + r.sum;
        re.mn = min(mn, sum + r.mn);
        re.mx = max(mx, sum + r.mx);
        return re;
    }
} node[SIZE * 4];

void upd(int pos, int l, int r, int p, int x) {
    if (l == r) {
        node[pos].sum += x;
        node[pos].mn = node[pos].mx = node[pos].sum;
        // debug(node[pos].sum, node[pos].mn, node[pos].mx);
        return;
    }
    int mid = (l + r) / 2;
    if (p <= mid) upd(lpos, l, mid, p, x);
    else upd(rpos, mid + 1, r, p, x);
    node[pos] = node[lpos] + node[rpos];
}
ll que(int pos, int l, int r, int L, int R) {
    if (l == L && r == R) return node[pos].sum;
    int mid = (L + R) / 2;
    if (r <= mid) return que(lpos, l, r, L, mid);
    if (l > mid) return que(rpos, l, r, mid + 1, R);
    return que(lpos, l, mid, L, mid) + que(rpos, mid + 1, r, mid + 1, R);
}
ll que(int l, int r) {
    if (l > r) return 0;
    return que(1, l, r, 0, q);
}
tuple<int, ll, ll> sch(int pos, int l, int r, int lim, ll psum = 0, ll pmx = -INF, ll pmn = INF) {
    if (l == r) return {l, max(pmx, psum + node[pos].mx), min(pmn, psum + node[pos].mn)};
    int mid = (l + r) / 2;
    ll lsum = psum + node[lpos].sum;
    ll rmx = max(pmx, lsum + node[rpos].mx);
    ll rmn = min(pmn, lsum + node[rpos].mn);
    if (rmx - rmn >= lim) return sch(rpos, mid + 1, r, lim, lsum, pmx, pmn);
    else return sch(lpos, l, mid, lim, psum, rmx, rmn);
}
int sch2(int pos, int l, int r, int ty, ll x, ll psum = 0, ll pmx = -INF, ll pmn = INF) {
    if (l == r) return l;
    int mid = (l + r) / 2;
    ll lsum = psum + node[lpos].sum;
    ll rmx = max(pmx, lsum + node[rpos].mx);
    ll rmn = min(pmn, lsum + node[rpos].mn);
    // debug(l, r, ty, x, lsum, rmx, rmn);
    if ((ty == 1 && rmn == x) || (ty == 0 && rmx == x)) return sch2(rpos, mid + 1, r, ty, x, lsum, pmx, pmn);
    else return sch2(lpos, l, mid, ty, x, psum, rmx, rmn);
}
int sch3(int pos, int l, int r) {
    if (l == r) return l;
    int mid = (l + r) / 2;
    ll rmn = node[lpos].sum + node[rpos].mn;
    if (rmn == node[pos].mn) return sch3(rpos, mid + 1, r);
    return sch3(lpos, l, mid);
}

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]) upd(1, 0, q, p, x);
        if (node[1].mx - node[1].mn < c[i]) {
            int p = sch3(1, 0, q);
            ans[i] = que(p + 1, q);
            // debug(p);
            continue;
        }
        auto [lp, mx, mn] = sch(1, 0, q, c[i]);
        int ty = (que(0, lp) == mx);
        int rp = sch2(1, 0, q, ty, (ty ? mn : mx));
        // debug(lp, rp, ty, mx, mn);
        ans[i] = (ty ? que(rp + 1, q) : c[i] + 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: 0 / 3
• Subtask 2: 8 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33