oj.uz

Submission #815414

# Submission time Handle Problem Language Result Execution time Memory
815414 2023-08-08T14:53:23 Z becaido Distributing Candies (IOI21_candies) C++17
100 / 100
 466 ms 31440 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
#include "candies.h"
using namespace std;

#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) {
        for (auto [p, x] : op[i]) upd(p, x);
        if (node[1].mx - node[1].mn <= c[i]) {
            int lp = sch_mn();
            ans[i] = que(lp + 1, q);
            continue;
        }
        auto [lp, ty] = sch_rdif(c[i]);
        int rp = sch(lp + 1, q, !ty);
        ans[i] = (ty == 0 ? c[i] : 0) + que(rp + 1, q);
    }
    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 4 ms 5176 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 5 ms 5204 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 31396 KB Output is correct
2 Correct 463 ms 31440 KB Output is correct
3 Correct 420 ms 31304 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 245 ms 26540 KB Output is correct
3 Correct 124 ms 8704 KB Output is correct
4 Correct 436 ms 31308 KB Output is correct
5 Correct 463 ms 31280 KB Output is correct
6 Correct 445 ms 31400 KB Output is correct
7 Correct 431 ms 31304 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 106 ms 25280 KB Output is correct
4 Correct 89 ms 7664 KB Output is correct
5 Correct 241 ms 27448 KB Output is correct
6 Correct 250 ms 27392 KB Output is correct
7 Correct 255 ms 27512 KB Output is correct
8 Correct 276 ms 27436 KB Output is correct
9 Correct 261 ms 27436 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 4 ms 5176 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 5 ms 5204 KB Output is correct
6 Correct 416 ms 31396 KB Output is correct
7 Correct 463 ms 31440 KB Output is correct
8 Correct 420 ms 31304 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 245 ms 26540 KB Output is correct
11 Correct 124 ms 8704 KB Output is correct
12 Correct 436 ms 31308 KB Output is correct
13 Correct 463 ms 31280 KB Output is correct
14 Correct 445 ms 31400 KB Output is correct
15 Correct 431 ms 31304 KB Output is correct
16 Correct 3 ms 4992 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 106 ms 25280 KB Output is correct
19 Correct 89 ms 7664 KB Output is correct
20 Correct 241 ms 27448 KB Output is correct
21 Correct 250 ms 27392 KB Output is correct
22 Correct 255 ms 27512 KB Output is correct
23 Correct 276 ms 27436 KB Output is correct
24 Correct 261 ms 27436 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Correct 84 ms 7620 KB Output is correct
27 Correct 231 ms 26428 KB Output is correct
28 Correct 405 ms 31420 KB Output is correct
29 Correct 454 ms 31424 KB Output is correct
30 Correct 450 ms 31392 KB Output is correct
31 Correct 465 ms 31400 KB Output is correct
32 Correct 466 ms 31316 KB Output is correct