oj.uz

Submission #591483

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

struct Op{
    ll add = 0, mi = INF, ma = -INF;
};
Op merge(Op a, Op b){
    Op c;
    c.add = a.add+b.add;
    c.mi = min(a.mi+b.add, b.mi);
    c.ma = max(a.ma+b.add, b.ma);
    return c;
}

int cap;
vector<Op> O;
vector<bool> lazy;

void apply(Op o, int i){
    O[i] = merge(O[i], o);
    lazy[i] = true;
}
void push(int i){
    if(lazy[i]){
        apply(O[i], 2*i);
        apply(O[i], 2*i+1);
        O[i] = Op();
        lazy[i] = false;
    }
}
void upd(int l, int r, Op x, int a, int b, int i){
    if(l <= a && b <= r) apply(x, i);
    else if(b < l || r < a) return;
    else{
        push(i);
        int m = (a+b)/2;
        upd(l, r, x, a, m, 2*i);
        upd(l, r, x, m+1, b, 2*i+1);
    }
}
void go(int p, int a, int b, int i){
    if(a == b) return;
    push(i);
    int m = (a+b)/2;
    if(p <= m) go(p, a, m, 2*i);
    else go(p, 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 < n; cap *= 2);
    O.resize(2*cap);
    lazy.resize(2*cap);

    for(int i = 0; i < q; i++){
        upd(l[i]+1, r[i]+1, {v[i], c[0], 0}, 1, cap, 1);
    }
    vector<int> ans(n);
    for(int i = 0; i < n; i++){
        go(i+1, 1, cap, 1);
        ans[i] = min(O[i+cap].mi, max(O[i+cap].ma, O[i+cap].add));
    }
    return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 413 ms 19688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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