oj.uz

Submission #479857

# Submission time Handle Problem Language Result Execution time Memory
479857 2021-10-13T15:38:04 Z couplefire Distributing Candies (IOI21_candies) C++17
100 / 100
 557 ms 46876 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 1<<18;

struct node{ll sum, mn, mx;} tree[N<<1];
int n, q, cap[N], q_l[N], q_r[N], val[N];
vector<int> start[N], stop[N], res;

node comb(node a, node b){
    node res; res.sum = a.sum+b.sum;
    res.mn = min(a.mn, a.sum+b.mn);
    res.mx = max(a.mx, a.sum+b.mx);
    return res;
}

void upd(int pos, int nval, int v = 1, int tl = 0, int tr = N-1){
    if(tr<pos || tl>pos) return;
    if(tl==tr) return void(tree[v] = {nval, min(nval, 0), max(nval, 0)});
    int tm = (tl+tr)>>1;
    upd(pos, nval, v<<1, tl, tm);
    upd(pos, nval, v<<1|1, tm+1, tr);
    tree[v] = comb(tree[v<<1], tree[v<<1|1]);
}

node get(int l, int r, int v = 1, int tl = 0, int tr = N-1){
    if(tr<l || tl>r) return {0, (ll)1e18, -(ll)1e18};
    if(l<=tl && tr<=r) return tree[v];
    int tm = (tl+tr)>>1;
    return comb(get(l, r, v<<1, tl, tm), get(l, r, v<<1|1, tm+1, tr));
}

int find(int bd, node nxt, int v = 1, int tl = 0, int tr = N-1){
    node tmp = comb(tree[v], nxt);
    if(tmp.mx-tmp.mn<(ll)bd) return -1;
    if(tl==tr) return tl;
    int tm = (tl+tr)>>1;
    int x = find(bd, nxt, v<<1|1, tm+1, tr);
    if(x>=0) return x;
    return find(bd, comb(tree[v<<1|1], nxt), v<<1, tl, tm);
}

vector<int> distribute_candies(vector<int> _c, vector<int> _l, vector<int> _r, vector<int> _v){
    n = _c.size(), q = _l.size();
    for(int i = 0; i<n; ++i) cap[i] = _c[i];
    for(int i = 0; i<q; ++i)
        q_l[i] = _l[i], q_r[i] = _r[i], val[i] = _v[i];
    for(int i = 0; i<q; ++i)
        start[q_l[i]].push_back(i), stop[q_r[i]].push_back(i);
    res.resize(n);
    for(int i = 0; i<n; ++i){
        for(auto x : start[i]) upd(x, val[x]);
        int pos = find(cap[i], {0, 0, 0});
        node cur = get(max(pos, 0), N-1);
        if(pos==-1 || cur.mx==0ll) res[i] = cur.sum-cur.mn;
        else res[i] = (ll)cap[i]-cur.mx+cur.sum;
        for(auto x : stop[i]) upd(x, 0);
    } return res;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12620 KB Output is correct
2 Correct 8 ms 12620 KB Output is correct
3 Correct 11 ms 12876 KB Output is correct
4 Correct 11 ms 12788 KB Output is correct
5 Correct 15 ms 13004 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 45032 KB Output is correct
2 Correct 511 ms 44372 KB Output is correct
3 Correct 554 ms 44104 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12620 KB Output is correct
2 Correct 236 ms 34964 KB Output is correct
3 Correct 169 ms 20152 KB Output is correct
4 Correct 502 ms 46124 KB Output is correct
5 Correct 512 ms 46492 KB Output is correct
6 Correct 489 ms 46876 KB Output is correct
7 Correct 487 ms 46120 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12620 KB Output is correct
2 Correct 7 ms 12620 KB Output is correct
3 Correct 167 ms 33416 KB Output is correct
4 Correct 135 ms 18092 KB Output is correct
5 Correct 268 ms 38220 KB Output is correct
6 Correct 292 ms 38972 KB Output is correct
7 Correct 314 ms 39520 KB Output is correct
8 Correct 293 ms 38196 KB Output is correct
9 Correct 317 ms 39680 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12620 KB Output is correct
2 Correct 8 ms 12620 KB Output is correct
3 Correct 11 ms 12876 KB Output is correct
4 Correct 11 ms 12788 KB Output is correct
5 Correct 15 ms 13004 KB Output is correct
6 Correct 491 ms 45032 KB Output is correct
7 Correct 511 ms 44372 KB Output is correct
8 Correct 554 ms 44104 KB Output is correct
9 Correct 8 ms 12620 KB Output is correct
10 Correct 236 ms 34964 KB Output is correct
11 Correct 169 ms 20152 KB Output is correct
12 Correct 502 ms 46124 KB Output is correct
13 Correct 512 ms 46492 KB Output is correct
14 Correct 489 ms 46876 KB Output is correct
15 Correct 487 ms 46120 KB Output is correct
16 Correct 7 ms 12620 KB Output is correct
17 Correct 7 ms 12620 KB Output is correct
18 Correct 167 ms 33416 KB Output is correct
19 Correct 135 ms 18092 KB Output is correct
20 Correct 268 ms 38220 KB Output is correct
21 Correct 292 ms 38972 KB Output is correct
22 Correct 314 ms 39520 KB Output is correct
23 Correct 293 ms 38196 KB Output is correct
24 Correct 317 ms 39680 KB Output is correct
25 Correct 7 ms 12612 KB Output is correct
26 Correct 132 ms 18084 KB Output is correct
27 Correct 261 ms 34528 KB Output is correct
28 Correct 482 ms 44744 KB Output is correct
29 Correct 509 ms 45120 KB Output is correct
30 Correct 557 ms 45380 KB Output is correct
31 Correct 490 ms 45508 KB Output is correct
32 Correct 483 ms 45680 KB Output is correct