oj.uz

Submission #583256

# Submission time Handle Problem Language Result Execution time Memory
583256 2022-06-25T06:52:06 Z SlavicG Distributing Candies (IOI21_candies) C++17
100 / 100
 3196 ms 93644 KB 
#include "bits/stdc++.h"
#include "candies.h"
using namespace std;

using ll = long long;
const ll inf = 1e16;
const int N = 4e5 + 10;
struct node {
    ll mn, mx, posmn, posmx;
};
node neutral = {inf, -inf, -1, -1};

node t[4 * N];
ll lazy[4 * N];

void push(int i, int l, int r) {
    if(!lazy[i]) return;
    t[i].mn += lazy[i];
    t[i].mx += lazy[i];
    if(l != r) {
        lazy[2 * i] += lazy[i];
        lazy[2 * i + 1] += lazy[i];
    }
    lazy[i] = 0;
}

node merge(node a, node b) {
    if(a.mn == -1) return b;
    if(b.mn == -1) return a;
    node c;
    c.mn = min(a.mn, b.mn);
    c.mx = max(a.mx, b.mx);
    c.posmn = (a.mn < b.mn ? a.posmn : b.posmn);
    c.posmx = (a.mx > b.mx ? a.posmx : b.posmx);
    return c;
}

void modif(int i, int l, int r, int tl, int tr, ll val) {
    push(i, l, r);
    if(l > tr || r < tl) return;
    if(l >= tl && r <= tr) {
        lazy[i] += val;
        push(i, l, r);
        return;
    }
    int mid = l + r >> 1;
    modif(2 * i, l, mid, tl, tr, val);
    modif(2 * i + 1, mid + 1, r, tl, tr, val);
    t[i] = merge(t[2 * i], t[2 * i + 1]);
}
node query(int i, int l, int r, int tl, int tr) {
    push(i, l, r);
    if(l > tr || r < tl) return neutral;
    if(l >= tl && r <= tr) return t[i];
    int mid = l + r >> 1;
    return merge(query(2 * i, l, mid, tl, tr), query(2 * i + 1, mid + 1, r, tl, tr));
}
void build(int i, int l, int r) {
    if(l > r) return;
    if(l == r) {
        t[i].mx = t[i].mn = 0;
        t[i].posmn = t[i].posmx = l;
        lazy[i] = 0;
        return;
    }
    int mid = l + r >> 1;
    build(2 * i, l, mid);
    build(2 * i + 1, mid + 1, r);
    t[i] = merge(t[2 * i], t[2 * i + 1]);
}
std::vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    for(int i = 0; i < 4 * N; ++i) t[i] = neutral, lazy[i] = 0;
    int n = c.size(), q = l.size();
    build(1, 0, q + 5);

    vector<ll> a(n, 0);
    vector<vector<int>> st(n + 1), en(n + 1);
    for(int i = 0; i < q; ++i) {
        st[l[i]].push_back(i);
        en[r[i] + 1].push_back(i);
    }

    for(int i = 0; i < n; ++i) {
        for(auto j: en[i]) {
            modif(1, 0, q + 5, j + 1, q, -v[j]);
        }
        for(auto j: st[i]) {
            modif(1, 0, q + 5, j + 1, q, v[j]);
        }
        if(query(1, 0, q + 5, q, q).mx - query(1, 0, q + 5, q - 1, q - 1).mx >= c[i]) {
            a[i] = c[i];
            continue;
        }
        if(query(1, 0, q + 5, q, q).mn - query(1, 0, q + 5, q - 1, q - 1).mn <= -c[i]) {
            a[i] = 0;
            continue;
        }
        int l = 0, r = q - 1, pos = -1;
        while(l <= r) {
            int mid = l + r >> 1;
            node x = query(1, 0, q + 5, mid, q);
            if(x.mx - x.mn >= c[i]) {
                pos = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        if(pos != -1) {
            node x = query(1, 0, q + 5, pos, q);
            if(x.posmx < x.posmn) {
                a[i] = 0;
            } else {
                a[i] = c[i];
            }
            int j = max(x.posmn, x.posmx);
            if(j + 1 <= q) {
                node x = query(1, 0, q + 5, j + 1, q);
                ll MN = x.mn - query(1, 0, q + 5, j, j).mn;
                ll MX = x.mx - query(1, 0, q + 5, j, j).mn;
                assert(MN > -c[i]);
                assert(MX < c[i]);
                if(!a[i] && MN < 0) a[i] -= MN;
                else if(a[i] == c[i] && MX > 0) a[i] -= MX;
                a[i] += query(1, 0, q + 5, q, q).mx - query(1, 0, q + 5, j, j).mx;
                assert(a[i] >= 0 && a[i] <= c[i]);
            }
        } else {
            node x = query(1, 0, q + 5, q, q);
            a[i] = x.mx;
            x = query(1, 0, q + 5, 0, q);
            if(x.mn < 0) a[i] -= x.mn;
            assert(a[i] >= 0 && a[i] <= c[i]);
        }
    }
    vector<int> cc(n);
    for(int i = 0; i < n; ++i) cc[i] = a[i];
    return cc;
}
/*
3
10 15 13
2
0 2 20
0 1 -11
*/

Compilation message

candies.cpp: In function 'void modif(int, int, int, int, int, ll)':
candies.cpp:46:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     int mid = l + r >> 1;
      |               ~~^~~
candies.cpp: In function 'node query(int, int, int, int, int)':
candies.cpp:55:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |     int mid = l + r >> 1;
      |               ~~^~~
candies.cpp: In function 'void build(int, int, int)':
candies.cpp:66:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |     int mid = l + r >> 1;
      |               ~~^~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:100:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |             int mid = l + r >> 1;
      |                       ~~^~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 62884 KB Output is correct
2 Correct 25 ms 62932 KB Output is correct
3 Correct 25 ms 62920 KB Output is correct
4 Correct 31 ms 62920 KB Output is correct
5 Correct 31 ms 63096 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2395 ms 88108 KB Output is correct
2 Correct 2482 ms 88112 KB Output is correct
3 Correct 2529 ms 88060 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 62856 KB Output is correct
2 Correct 454 ms 70584 KB Output is correct
3 Correct 1117 ms 76392 KB Output is correct
4 Correct 3094 ms 88116 KB Output is correct
5 Correct 3196 ms 88108 KB Output is correct
6 Correct 2422 ms 88120 KB Output is correct
7 Correct 2473 ms 88180 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 62876 KB Output is correct
2 Correct 25 ms 62932 KB Output is correct
3 Correct 208 ms 69484 KB Output is correct
4 Correct 515 ms 76288 KB Output is correct
5 Correct 1835 ms 82720 KB Output is correct
6 Correct 1941 ms 82744 KB Output is correct
7 Correct 624 ms 82716 KB Output is correct
8 Correct 1868 ms 82724 KB Output is correct
9 Correct 2403 ms 82744 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 62884 KB Output is correct
2 Correct 25 ms 62932 KB Output is correct
3 Correct 25 ms 62920 KB Output is correct
4 Correct 31 ms 62920 KB Output is correct
5 Correct 31 ms 63096 KB Output is correct
6 Correct 2395 ms 88108 KB Output is correct
7 Correct 2482 ms 88112 KB Output is correct
8 Correct 2529 ms 88060 KB Output is correct
9 Correct 24 ms 62856 KB Output is correct
10 Correct 454 ms 70584 KB Output is correct
11 Correct 1117 ms 76392 KB Output is correct
12 Correct 3094 ms 88116 KB Output is correct
13 Correct 3196 ms 88108 KB Output is correct
14 Correct 2422 ms 88120 KB Output is correct
15 Correct 2473 ms 88180 KB Output is correct
16 Correct 24 ms 62876 KB Output is correct
17 Correct 25 ms 62932 KB Output is correct
18 Correct 208 ms 69484 KB Output is correct
19 Correct 515 ms 76288 KB Output is correct
20 Correct 1835 ms 82720 KB Output is correct
21 Correct 1941 ms 82744 KB Output is correct
22 Correct 624 ms 82716 KB Output is correct
23 Correct 1868 ms 82724 KB Output is correct
24 Correct 2403 ms 82744 KB Output is correct
25 Correct 24 ms 62804 KB Output is correct
26 Correct 802 ms 76388 KB Output is correct
27 Correct 445 ms 70504 KB Output is correct
28 Correct 2538 ms 88108 KB Output is correct
29 Correct 2336 ms 93052 KB Output is correct
30 Correct 2368 ms 93344 KB Output is correct
31 Correct 2246 ms 93432 KB Output is correct
32 Correct 1658 ms 93644 KB Output is correct