oj.uz

Submission #590779

# Submission time Handle Problem Language Result Execution time Memory
590779 2022-07-06T11:02:28 Z Lucpp Distributing Candies (IOI21_candies) C++17
37 / 100
 3164 ms 39612 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, q});
    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;
    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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 2 ms 596 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3011 ms 39612 KB Output is correct
2 Correct 3139 ms 39608 KB Output is correct
3 Correct 3164 ms 39604 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 456 ms 30092 KB Output isn't correct
3 Halted 0 ms 0 KB -

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 212 KB Output is correct
3 Correct 181 ms 28952 KB Output is correct
4 Correct 867 ms 7604 KB Output is correct
5 Correct 2835 ms 35728 KB Output is correct
6 Correct 2740 ms 35732 KB Output is correct
7 Correct 2453 ms 35728 KB Output is correct
8 Correct 2738 ms 35884 KB Output is correct
9 Correct 2827 ms 35728 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 2 ms 596 KB Output isn't correct
4 Halted 0 ms 0 KB -