oj.uz

Submission #623255

# Submission time Handle Problem Language Result Execution time Memory
623255 2022-08-05T11:20:43 Z cheissmart Distributing Candies (IOI21_candies) C++17
100 / 100
 1507 ms 45388 KB 
#include "candies.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 2e5 + 7;
const ll oo = 1e18;

int c[N], n, q;
V<pi> ev[N];

namespace brute {
    ll a[N];
    void add(int l, int r, int x) {
        assert(0 <= l && l < r && r <= q + 1);
        for(int i = l; i < r; i++) {
            a[i] += x;
        }
    }
    ll qmax(int l, int r) {
        assert(0 <= l && l < r && r <= q + 1);
        ll mx = -oo;
        for(int i = l; i < r; i++) {
            mx = max(mx, a[i]);
        }
        return mx;
    }
    ll qmin(int l, int r) {
        assert(0 <= l && l < r && r <= q + 1);
        ll mn = oo;
        for(int i = l; i < r; i++) {
            mn = min(mn, a[i]);
        }
        return mn;
    }
}

namespace DS {

struct node {
    ll mn, mx, lz;
    node() {
        mn = mx = lz = 0;
    }
} t[N * 4];

void apply(int v, ll x) {
    t[v].lz += x;
    t[v].mn += x;
    t[v].mx += x;
}
void push(int v) {
    apply(v * 2, t[v].lz);
    apply(v * 2 + 1, t[v].lz);
    t[v].lz = 0;
}
void pull(int v) {
    t[v].mn = min(t[v * 2].mn, t[v * 2 + 1].mn);
    t[v].mx = max(t[v * 2].mx, t[v * 2 + 1].mx);
}

void add(int l, int r, ll x, int v = 1, int tl = 0, int tr = q + 1) {
    if(l <= tl && tr <= r) {
        apply(v, x);
        return;
    }
    push(v);
    int tm = (tl + tr) / 2;
    if(l < tm) add(l, r, x, v * 2, tl, tm);
    if(r > tm) add(l, r, x, v * 2 + 1, tm, tr);
    pull(v);
}

ll qmin(int l, int r, int v = 1, int tl = 0, int tr = q + 1){
    if(l <= tl && tr <= r)
        return t[v].mn;
    push(v);
    int tm = (tl + tr) / 2;
    ll res = oo;
    if(l < tm) res = min(res, qmin(l, r, v * 2, tl, tm));
    if(r > tm) res = min(res, qmin(l, r, v * 2 + 1, tm, tr));
    return res;
}

ll qmax(int l, int r, int v = 1, int tl = 0, int tr = q + 1){
    if(l <= tl && tr <= r)
        return t[v].mx;
    push(v);
    int tm = (tl + tr) / 2;
    ll res = -oo;
    if(l < tm) res = max(res, qmax(l, r, v * 2, tl, tm));
    if(r > tm) res = max(res, qmax(l, r, v * 2 + 1, tm, tr));
    return res;
}

}

using namespace DS;

vi distribute_candies(vi _c, vi _l, vi _r, vi _v) {
    n = SZ(_c), q = SZ(_l);
    for(int i = 0; i < n; i++)
        c[i] = _c[i];

    vi ans(n);

    for(int i = 1; i <= q; i++) {
        int l = _l[i - 1], r = _r[i - 1], v = _v[i - 1];
        ev[l].EB(i, v);
        ev[r + 1].EB(i, -v);
    }

    for(int i = 0; i < n; i++) {
        for(auto [pos, val]:ev[i]) {
            add(pos, q + 1, val);
        }
        ll final = qmax(q, q + 1);
        ll mx = qmax(0, q + 1);
        ll mn = qmin(0, q + 1);
        if(mx - mn <= c[i]) {
            ans[i] = final - mn;
        } else {
            int lb = 0, rb = q;
            while(lb <= rb) {
                int mb = (lb + rb) / 2;
                ll mx = qmax(mb, q + 1);
                ll mn = qmin(mb, q + 1);
                if(mx - mn <= c[i])
                    rb = mb - 1;
                else
                    lb = mb + 1;
            }
            ll mx = qmax(rb, q + 1);
            ll mn = qmin(rb, q + 1);
            assert(mx - mn > c[i]);
            ll val = qmax(rb, rb + 1);
            if(val == mx) {
                ans[i] = final - mn;
            } else {
                ans[i] = final - (mx - c[i]);
            }
        }
    }

    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 11 ms 23732 KB Output is correct
3 Correct 12 ms 23892 KB Output is correct
4 Correct 14 ms 23884 KB Output is correct
5 Correct 15 ms 23904 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 945 ms 38660 KB Output is correct
2 Correct 949 ms 42816 KB Output is correct
3 Correct 876 ms 42568 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23820 KB Output is correct
2 Correct 200 ms 32924 KB Output is correct
3 Correct 460 ms 28228 KB Output is correct
4 Correct 1507 ms 38712 KB Output is correct
5 Correct 1061 ms 44988 KB Output is correct
6 Correct 921 ms 45388 KB Output is correct
7 Correct 905 ms 44712 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 110 ms 31704 KB Output is correct
4 Correct 249 ms 27196 KB Output is correct
5 Correct 596 ms 34992 KB Output is correct
6 Correct 675 ms 34992 KB Output is correct
7 Correct 742 ms 35092 KB Output is correct
8 Correct 585 ms 35096 KB Output is correct
9 Correct 1415 ms 34992 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 11 ms 23732 KB Output is correct
3 Correct 12 ms 23892 KB Output is correct
4 Correct 14 ms 23884 KB Output is correct
5 Correct 15 ms 23904 KB Output is correct
6 Correct 945 ms 38660 KB Output is correct
7 Correct 949 ms 42816 KB Output is correct
8 Correct 876 ms 42568 KB Output is correct
9 Correct 16 ms 23820 KB Output is correct
10 Correct 200 ms 32924 KB Output is correct
11 Correct 460 ms 28228 KB Output is correct
12 Correct 1507 ms 38712 KB Output is correct
13 Correct 1061 ms 44988 KB Output is correct
14 Correct 921 ms 45388 KB Output is correct
15 Correct 905 ms 44712 KB Output is correct
16 Correct 11 ms 23764 KB Output is correct
17 Correct 12 ms 23764 KB Output is correct
18 Correct 110 ms 31704 KB Output is correct
19 Correct 249 ms 27196 KB Output is correct
20 Correct 596 ms 34992 KB Output is correct
21 Correct 675 ms 34992 KB Output is correct
22 Correct 742 ms 35092 KB Output is correct
23 Correct 585 ms 35096 KB Output is correct
24 Correct 1415 ms 34992 KB Output is correct
25 Correct 11 ms 23764 KB Output is correct
26 Correct 195 ms 28316 KB Output is correct
27 Correct 198 ms 35660 KB Output is correct
28 Correct 735 ms 43272 KB Output is correct
29 Correct 832 ms 43672 KB Output is correct
30 Correct 922 ms 43824 KB Output is correct
31 Correct 988 ms 44008 KB Output is correct
32 Correct 1002 ms 44196 KB Output is correct