oj.uz

Submission #815864

# Submission time Handle Problem Language Result Execution time Memory
815864 2023-08-09T01:42:45 Z becaido Distributing Candies (IOI21_candies) C++17
100 / 100
 436 ms 36916 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) {
    if (!node[pos].lazy) return;
    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 3 ms 4948 KB Output is correct
2 Correct 3 ms 5000 KB Output is correct
3 Correct 4 ms 5148 KB Output is correct
4 Correct 4 ms 5144 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 384 ms 31536 KB Output is correct
2 Correct 386 ms 31532 KB Output is correct
3 Correct 417 ms 31528 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 223 ms 26632 KB Output is correct
3 Correct 83 ms 8884 KB Output is correct
4 Correct 410 ms 31568 KB Output is correct
5 Correct 436 ms 31540 KB Output is correct
6 Correct 407 ms 31524 KB Output is correct
7 Correct 376 ms 31528 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 4 ms 4948 KB Output is correct
3 Correct 94 ms 25440 KB Output is correct
4 Correct 99 ms 7836 KB Output is correct
5 Correct 183 ms 27776 KB Output is correct
6 Correct 195 ms 27696 KB Output is correct
7 Correct 207 ms 27776 KB Output is correct
8 Correct 195 ms 27704 KB Output is correct
9 Correct 227 ms 27696 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5000 KB Output is correct
3 Correct 4 ms 5148 KB Output is correct
4 Correct 4 ms 5144 KB Output is correct
5 Correct 5 ms 5204 KB Output is correct
6 Correct 384 ms 31536 KB Output is correct
7 Correct 386 ms 31532 KB Output is correct
8 Correct 417 ms 31528 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 223 ms 26632 KB Output is correct
11 Correct 83 ms 8884 KB Output is correct
12 Correct 410 ms 31568 KB Output is correct
13 Correct 436 ms 31540 KB Output is correct
14 Correct 407 ms 31524 KB Output is correct
15 Correct 376 ms 31528 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 4 ms 4948 KB Output is correct
18 Correct 94 ms 25440 KB Output is correct
19 Correct 99 ms 7836 KB Output is correct
20 Correct 183 ms 27776 KB Output is correct
21 Correct 195 ms 27696 KB Output is correct
22 Correct 207 ms 27776 KB Output is correct
23 Correct 195 ms 27704 KB Output is correct
24 Correct 227 ms 27696 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Correct 67 ms 7892 KB Output is correct
27 Correct 214 ms 29004 KB Output is correct
28 Correct 390 ms 35960 KB Output is correct
29 Correct 413 ms 36404 KB Output is correct
30 Correct 421 ms 36532 KB Output is correct
31 Correct 409 ms 36624 KB Output is correct
32 Correct 428 ms 36916 KB Output is correct