oj.uz

Submission #837743

# Submission time Handle Problem Language Result Execution time Memory
837743 2023-08-25T15:19:01 Z Kerim Distributing Candies (IOI21_candies) C++17
100 / 100
 760 ms 44196 KB 
#include "candies.h"
#include "bits/stdc++.h"
#define ll long long
using namespace std;
const int N = 2e5+5;
vector<int> add[N], rem[N];
int arr[N];
struct node{
    ll mx, mn, sum;
    node(){
        mx = mn = sum = 0;
    }
    node(int v){
        mx = max(0, v);
        mn = min(0, v);
        sum = v;
    }
}s[N<<2];
node merge(node x, node y){
    node z;
    z.sum = x.sum + y.sum;
    z.mn = min(y.mn, x.mn + y.sum);
    z.mx = max(y.mx, x.mx + y.sum);
    return z;
}
void upd(int p, int v, int nd, int x, int y){
    if (x == y){
        arr[p] = v;
        s[nd] = node(v);
        return;
    }
    int mid = (x+y) >> 1;
    if (p <= mid)
        upd(p, v, nd << 1, x, mid);
    else    
        upd(p, v, nd<<1|1, mid+1, y);
    s[nd] = merge(s[nd<<1], s[nd<<1|1]);
}
node get(int l, int r, int nd, int x, int y){
    if (l > y or x > r)
        return node();
    if (l <= x and y <= r)
        return s[nd];
    int mid = (x+y) >> 1;
    return merge(get(l, r, nd<<1, x, mid), get(l, r, nd<<1|1, mid+1, y));
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size(), q = l.size();
    vector<int> s(n);
    for (int i = 0; i < q; i++){
        add[l[i]].push_back(i);
        rem[r[i]].push_back(i);
    }
    for (int i = 0; i < n; i++){
        for (auto pos: add[i])
            upd(pos, v[pos], 1, 0, q-1);
        int st = -1, en = q-1;
        while (st < en){
            int mid = (st + en + 1) >> 1;
            node res = get(mid, q-1, 1, 0, q-1);
            if (res.mx - res.mn > c[i])
                st = mid;
            else
                en = mid-1;
        }
        node res = get(max(st, 0), q-1, 1, 0, q-1);
        if (st >= 0){
            if (arr[st] > 0)
                s[i] = c[i] + res.mn;
            else
                s[i] = res.mx;
        }
        else    
            s[i] = res.mx;
        for (auto pos: rem[i])
            upd(pos, 0, 1, 0, q-1);
    }
    return s;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 28372 KB Output is correct
2 Correct 13 ms 28372 KB Output is correct
3 Correct 13 ms 28500 KB Output is correct
4 Correct 13 ms 28500 KB Output is correct
5 Correct 17 ms 28572 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 722 ms 43632 KB Output is correct
2 Correct 727 ms 43636 KB Output is correct
3 Correct 745 ms 43644 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28500 KB Output is correct
2 Correct 174 ms 36956 KB Output is correct
3 Correct 239 ms 32276 KB Output is correct
4 Correct 760 ms 43624 KB Output is correct
5 Correct 714 ms 43684 KB Output is correct
6 Correct 640 ms 43708 KB Output is correct
7 Correct 666 ms 43680 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 28496 KB Output is correct
2 Correct 11 ms 28500 KB Output is correct
3 Correct 102 ms 35816 KB Output is correct
4 Correct 217 ms 31156 KB Output is correct
5 Correct 559 ms 38252 KB Output is correct
6 Correct 556 ms 38248 KB Output is correct
7 Correct 532 ms 38260 KB Output is correct
8 Correct 560 ms 38260 KB Output is correct
9 Correct 670 ms 38168 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 28372 KB Output is correct
2 Correct 13 ms 28372 KB Output is correct
3 Correct 13 ms 28500 KB Output is correct
4 Correct 13 ms 28500 KB Output is correct
5 Correct 17 ms 28572 KB Output is correct
6 Correct 722 ms 43632 KB Output is correct
7 Correct 727 ms 43636 KB Output is correct
8 Correct 745 ms 43644 KB Output is correct
9 Correct 13 ms 28500 KB Output is correct
10 Correct 174 ms 36956 KB Output is correct
11 Correct 239 ms 32276 KB Output is correct
12 Correct 760 ms 43624 KB Output is correct
13 Correct 714 ms 43684 KB Output is correct
14 Correct 640 ms 43708 KB Output is correct
15 Correct 666 ms 43680 KB Output is correct
16 Correct 12 ms 28496 KB Output is correct
17 Correct 11 ms 28500 KB Output is correct
18 Correct 102 ms 35816 KB Output is correct
19 Correct 217 ms 31156 KB Output is correct
20 Correct 559 ms 38252 KB Output is correct
21 Correct 556 ms 38248 KB Output is correct
22 Correct 532 ms 38260 KB Output is correct
23 Correct 560 ms 38260 KB Output is correct
24 Correct 670 ms 38168 KB Output is correct
25 Correct 11 ms 28372 KB Output is correct
26 Correct 197 ms 31644 KB Output is correct
27 Correct 149 ms 37468 KB Output is correct
28 Correct 688 ms 44116 KB Output is correct
29 Correct 690 ms 44140 KB Output is correct
30 Correct 703 ms 44136 KB Output is correct
31 Correct 677 ms 44196 KB Output is correct
32 Correct 684 ms 44156 KB Output is correct