oj.uz

Submission #815412

# Submission time Handle Problem Language Result Execution time Memory
815412 2023-08-08T14:51:09 Z becaido Distributing Candies (IOI21_candies) C++17
100 / 100
 508 ms 38076 KB 
#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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5012 KB Output is correct
2 Correct 3 ms 5004 KB Output is correct
3 Correct 4 ms 5144 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 5 ms 5192 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 36132 KB Output is correct
2 Correct 441 ms 35472 KB Output is correct
3 Correct 426 ms 35304 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 216 ms 29456 KB Output is correct
3 Correct 105 ms 10948 KB Output is correct
4 Correct 508 ms 37312 KB Output is correct
5 Correct 452 ms 37716 KB Output is correct
6 Correct 440 ms 38076 KB Output is correct
7 Correct 441 ms 37436 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5012 KB Output is correct
3 Correct 107 ms 27844 KB Output is correct
4 Correct 101 ms 8816 KB Output is correct
5 Correct 241 ms 31000 KB Output is correct
6 Correct 270 ms 31604 KB Output is correct
7 Correct 262 ms 32284 KB Output is correct
8 Correct 238 ms 30924 KB Output is correct
9 Correct 267 ms 32332 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5012 KB Output is correct
2 Correct 3 ms 5004 KB Output is correct
3 Correct 4 ms 5144 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 5 ms 5192 KB Output is correct
6 Correct 455 ms 36132 KB Output is correct
7 Correct 441 ms 35472 KB Output is correct
8 Correct 426 ms 35304 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 216 ms 29456 KB Output is correct
11 Correct 105 ms 10948 KB Output is correct
12 Correct 508 ms 37312 KB Output is correct
13 Correct 452 ms 37716 KB Output is correct
14 Correct 440 ms 38076 KB Output is correct
15 Correct 441 ms 37436 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 5012 KB Output is correct
18 Correct 107 ms 27844 KB Output is correct
19 Correct 101 ms 8816 KB Output is correct
20 Correct 241 ms 31000 KB Output is correct
21 Correct 270 ms 31604 KB Output is correct
22 Correct 262 ms 32284 KB Output is correct
23 Correct 238 ms 30924 KB Output is correct
24 Correct 267 ms 32332 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Correct 84 ms 8792 KB Output is correct
27 Correct 217 ms 29100 KB Output is correct
28 Correct 425 ms 36044 KB Output is correct
29 Correct 428 ms 36432 KB Output is correct
30 Correct 475 ms 36808 KB Output is correct
31 Correct 427 ms 36616 KB Output is correct
32 Correct 439 ms 36880 KB Output is correct