oj.uz

Submission #591039

# Submission time Handle Problem Language Result Execution time Memory
591039 2022-07-06T18:48:03 Z Lucpp Distributing Candies (IOI21_candies) C++17
100 / 100
 3359 ms 46304 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

int cap;
vector<pair<ll, int>> Smi, Sma;
vector<ll> O;

void apply(ll v, int i){
    Smi[i].first += v;
    Sma[i].first += v;
    O[i] += v;
}
void push(int i){
    if(O[i] != 0){
        apply(O[i], 2*i);
        apply(O[i], 2*i+1);
        O[i] = 0;
    }
}
void add(int l, int r, ll v, int a, int b, int i){
    if(l <= a && b <= r) apply(v, i);
    else if(b < l || r < a) return;
    else{
        push(i);
        int m = (a+b)/2;
        add(l, r, v, a, m, 2*i);
        add(l, r, v, m+1, b, 2*i+1);
        Smi[i] = min(Smi[2*i], Smi[2*i+1]);
        Sma[i] = max(Sma[2*i], Sma[2*i+1]);
    }
}

pair<ll, int> qryMi(int l, int r, int a, int b, int i){
    if(l <= a && b <= r) return Smi[i];
    else if(b < l || r < a) return {INF, 0};
    push(i);
    int m = (a+b)/2;
    return min(qryMi(l, r, a, m, 2*i), qryMi(l, r, m+1, b, 2*i+1));
}
pair<ll, int> qryMa(int l, int r, int a, int b, int i){
    if(l <= a && b <= r) return Sma[i];
    else if(b < l || r < a) return {-INF, 0};
    push(i);
    int m = (a+b)/2;
    return max(qryMa(l, r, a, m, 2*i), qryMa(l, r, m+1, b, 2*i+1));
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = (int)c.size();
    int q = (int)l.size();
    for(cap = 1; cap <= q; cap *= 2);
    Smi.assign(2*cap, {0, 0});
    Sma.assign(2*cap, {0, 0});
    O.assign(2*cap, 0);
    for(int i = 0; i < cap; i++) Smi[i+cap].second = Sma[i+cap].second = i;
    for(int i = q+1; i < cap; i++) Smi[i+cap].first = INF, Sma[i+cap].first = -INF;
    for(int i = cap-1; i >= 1; i--) Smi[i] = min(Smi[2*i], Smi[2*i+1]), Sma[i] = max(Sma[2*i], Sma[2*i+1]);
    vector<vector<pair<int, int>>> todo(n+1);
    for(int i = 0; i < q; i++){
        todo[l[i]].emplace_back(i, 1);
        todo[r[i]+1].emplace_back(i, -1);
    }
    vector<int> ans(n);
    for(int i = 0; i < n; i++){
        for(auto [j, op] : todo[i]){
            add(j+2, q+1, v[j]*op, 1, cap, 1);
        }
        int lo = 1, hi = q+1;
        for(int mid=(lo+hi)/2; lo<hi; mid=(lo+hi)/2){
            if(qryMa(mid, q+1, 1, cap, 1).first - qryMi(mid, q+1, 1, cap, 1).first <= c[i]) hi = mid;
            else lo = mid+1;
        }
        lo--;
        auto mi = qryMi(lo, q+1, 1, cap, 1);
        auto ma = qryMa(lo, q+1, 1, cap, 1);
        ll cur = qryMi(q+1, q+1, 1, cap, 1).first;
        // cerr << cur << " " << mi.second << " " << ma.second << "\n";
        if(ma.first-mi.first > c[i]){
            if(mi.second < ma.second) ans[i] = int(cur-ma.first+c[i]);
            else ans[i] = int(cur-mi.first);
        }
        else{
            ans[i] = int(cur-mi.first);
        }
    }
    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 14 ms 680 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3008 ms 44456 KB Output is correct
2 Correct 3167 ms 43684 KB Output is correct
3 Correct 3262 ms 43512 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 459 ms 33108 KB Output is correct
3 Correct 1034 ms 9860 KB Output is correct
4 Correct 3359 ms 45524 KB Output is correct
5 Correct 3355 ms 45980 KB Output is correct
6 Correct 3000 ms 46304 KB Output is correct
7 Correct 2912 ms 45648 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 205 ms 31660 KB Output is correct
4 Correct 909 ms 8808 KB Output is correct
5 Correct 2747 ms 39232 KB Output is correct
6 Correct 2634 ms 39908 KB Output is correct
7 Correct 2443 ms 40492 KB Output is correct
8 Correct 2789 ms 39136 KB Output is correct
9 Correct 2973 ms 40608 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 14 ms 680 KB Output is correct
6 Correct 3008 ms 44456 KB Output is correct
7 Correct 3167 ms 43684 KB Output is correct
8 Correct 3262 ms 43512 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 459 ms 33108 KB Output is correct
11 Correct 1034 ms 9860 KB Output is correct
12 Correct 3359 ms 45524 KB Output is correct
13 Correct 3355 ms 45980 KB Output is correct
14 Correct 3000 ms 46304 KB Output is correct
15 Correct 2912 ms 45648 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 300 KB Output is correct
18 Correct 205 ms 31660 KB Output is correct
19 Correct 909 ms 8808 KB Output is correct
20 Correct 2747 ms 39232 KB Output is correct
21 Correct 2634 ms 39908 KB Output is correct
22 Correct 2443 ms 40492 KB Output is correct
23 Correct 2789 ms 39136 KB Output is correct
24 Correct 2973 ms 40608 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 974 ms 8876 KB Output is correct
27 Correct 464 ms 32696 KB Output is correct
28 Correct 3221 ms 44168 KB Output is correct
29 Correct 3124 ms 44584 KB Output is correct
30 Correct 3004 ms 44736 KB Output is correct
31 Correct 3056 ms 44932 KB Output is correct
32 Correct 2856 ms 45128 KB Output is correct