oj.uz

Submission #1025768

# Submission time Handle Problem Language Result Execution time Memory
1025768 2024-07-17T09:49:01 Z thinknoexit Distributing Candies (IOI21_candies) C++17
100 / 100
 675 ms 44732 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200200;
int n;
struct A {
    ll mn, mx;
    A() {
        mn = mx = 0ll;
    }
    A operator + (const A& o) const {
        A t;
        t.mn = min(mn, o.mn);
        t.mx = max(mx, o.mx);
        return t;
    }
} tree[4 * N], _T;
ll lazy[4 * N];
void lzy(int now, int l, int r) {
    if (!lazy[now]) return;
    tree[now].mn += lazy[now];
    tree[now].mx += lazy[now];
    if (l != r) {
        lazy[2 * now] += lazy[now];
        lazy[2 * now + 1] += lazy[now];
    }
    lazy[now] = 0;
}
void update(int ql, int qr, ll w, int now = 1, int l = 0, int r = n) {
    lzy(now, l, r);
    if (l > qr || r < ql) return;
    if (ql <= l && r <= qr) {
        lazy[now] += w;
        lzy(now, l, r);
        return;
    }
    int mid = (l + r) / 2;
    update(ql, qr, w, 2 * now, l, mid);
    update(ql, qr, w, 2 * now + 1, mid + 1, r);
    tree[now] = tree[2 * now] + tree[2 * now + 1];
}
A query(int ql, int qr, int now = 1, int l = 0, int r = n) {
    lzy(now, l, r);
    if (ql <= l && r <= qr) return tree[now];
    int mid = (l + r) / 2;
    if (qr <= mid) return query(ql, qr, 2 * now, l, mid);
    if (ql > mid) return query(ql, qr, 2 * now + 1, mid + 1, r);
    return query(ql, qr, 2 * now, l, mid) + query(ql, qr, 2 * now + 1, mid + 1, r);
}
vector<pair<int, int>> q[N];
vector<int> distribute_candies(vector<int> c, vector<int> _l, vector<int> _r, vector<int> _v) {
    n = _l.size();
    int m = c.size();
    vector<int> ans(m);
    for (int i = 0;i < n;i++) {
        q[_l[i]].push_back({ _v[i], i + 1 });
        q[_r[i] + 1].push_back({ -_v[i], i + 1 });
    }
    // find last point that mx - mn <= c[i]
    ll sum = 0;
    for (int i = 0;i < m;i++) {
        for (auto& x : q[i]) {
            update(x.second, n, x.first);
            sum += x.first;
        }
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r) / 2;
            A now = query(mid, n);
            if (now.mx - now.mn <= c[i]) r = mid;
            else l = mid + 1;
        }
        if (l == 0) {
            ans[i] = sum - query(0, n).mn;
            continue;
        }
        A now = query(l, n);
        ll prev = query(l - 1, l - 1).mn;
        if (prev < now.mn) {
            ans[i] = sum - (now.mx - c[i]);
        }
        else {
            ans[i] = sum - now.mn;
        }
    }
    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19804 KB Output is correct
2 Correct 3 ms 19804 KB Output is correct
3 Correct 4 ms 19804 KB Output is correct
4 Correct 4 ms 19804 KB Output is correct
5 Correct 6 ms 19804 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 37968 KB Output is correct
2 Correct 518 ms 37968 KB Output is correct
3 Correct 562 ms 38016 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19800 KB Output is correct
2 Correct 173 ms 36140 KB Output is correct
3 Correct 150 ms 25664 KB Output is correct
4 Correct 562 ms 43844 KB Output is correct
5 Correct 529 ms 44340 KB Output is correct
6 Correct 517 ms 44732 KB Output is correct
7 Correct 418 ms 44072 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19800 KB Output is correct
2 Correct 3 ms 19804 KB Output is correct
3 Correct 94 ms 34484 KB Output is correct
4 Correct 115 ms 23496 KB Output is correct
5 Correct 398 ms 37876 KB Output is correct
6 Correct 321 ms 38416 KB Output is correct
7 Correct 274 ms 39092 KB Output is correct
8 Correct 345 ms 37512 KB Output is correct
9 Correct 454 ms 39408 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19804 KB Output is correct
2 Correct 3 ms 19804 KB Output is correct
3 Correct 4 ms 19804 KB Output is correct
4 Correct 4 ms 19804 KB Output is correct
5 Correct 6 ms 19804 KB Output is correct
6 Correct 472 ms 37968 KB Output is correct
7 Correct 518 ms 37968 KB Output is correct
8 Correct 562 ms 38016 KB Output is correct
9 Correct 3 ms 19800 KB Output is correct
10 Correct 173 ms 36140 KB Output is correct
11 Correct 150 ms 25664 KB Output is correct
12 Correct 562 ms 43844 KB Output is correct
13 Correct 529 ms 44340 KB Output is correct
14 Correct 517 ms 44732 KB Output is correct
15 Correct 418 ms 44072 KB Output is correct
16 Correct 4 ms 19800 KB Output is correct
17 Correct 3 ms 19804 KB Output is correct
18 Correct 94 ms 34484 KB Output is correct
19 Correct 115 ms 23496 KB Output is correct
20 Correct 398 ms 37876 KB Output is correct
21 Correct 321 ms 38416 KB Output is correct
22 Correct 274 ms 39092 KB Output is correct
23 Correct 345 ms 37512 KB Output is correct
24 Correct 454 ms 39408 KB Output is correct
25 Correct 4 ms 19764 KB Output is correct
26 Correct 139 ms 23560 KB Output is correct
27 Correct 268 ms 35760 KB Output is correct
28 Correct 675 ms 42576 KB Output is correct
29 Correct 599 ms 42756 KB Output is correct
30 Correct 594 ms 43160 KB Output is correct
31 Correct 570 ms 43360 KB Output is correct
32 Correct 503 ms 43308 KB Output is correct