oj.uz

Submission #837176

# Submission time Handle Problem Language Result Execution time Memory
837176 2023-08-25T07:05:08 Z QwertyPi Distributing Candies (IOI21_candies) C++17
8 / 100
 298 ms 41784 KB 
#include "candies.h"
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N_MAX = 2e5 + 11;
int n, q;

struct node{
    int pref_max, pref_min, sum;
    node() : pref_max(0), pref_min(0), sum(0){}
    node(int v) : pref_max(max(0LL, v)), pref_min(min(0LL, v)), sum(v){};
};

struct update{
    int t, pos, val;
};

node operator+ (const node& a, const node& b){
    node res;
    res.pref_max = max(a.pref_max, a.sum + b.pref_max);
    res.pref_min = min(a.pref_min, a.sum + b.pref_min);
    res.sum = a.sum + b.sum;
    return res;
}

node t[N_MAX << 2];
int a[N_MAX];

void st_update(int qi, int qv, int v = 0, int l = 0, int r = q - 1){
    if(l == r) t[v] = node(qv), a[qi] = qv;
    else {
        int m = (l + r) / 2;
        if(qi <= m) st_update(qi, qv, v * 2 + 1, l, m);
        else st_update(qi, qv, v * 2 + 2, m + 1, r);
        t[v] = t[v * 2 + 1] + t[v * 2 + 2];
    }
}

node st_suffix(int qi, int v = 0, int l = 0, int r = q - 1){
    if(qi > r) return 0;
    if(l == r) return t[v];
    else {
        int m = (l + r) / 2;
        if(qi <= m) return st_suffix(qi, v * 2 + 1, l, m) + t[v * 2 + 2];
        else return st_suffix(qi, v * 2 + 2, m + 1, r);
    }
}

int st_position(int c, node s = 0, int v = 0, int l = 0, int r = q - 1){
    if(l == r) return l;
    else {
        int m = (l + r) / 2;
        node s2 = t[v * 2 + 2] + s;
        if(s2.pref_max - s2.pref_min < c) return st_position(c, s2, v * 2 + 1, l, m);
        else return st_position(c, s, v * 2 + 2, m + 1, r);
    }
}

int f(node v, int x, int c){
    if(v.pref_max - v.pref_min < c){
        if(x > c - v.pref_max) x = c - v.pref_max;
        if(x < -v.pref_min) x = v.pref_min;
        return x + v.sum;
    }else{
        x += v.sum;
        if(x < 0) x = 0;
        if(x > c) x = c;
        return x;
    }
}

vector<int32_t> distribute_candies(vector<int32_t> c, vector<int32_t> l, vector<int32_t> r, vector<int32_t> v) {
    n = c.size(), q = l.size();
    vector<update> Q;
    for(int i = 0; i < q; i++){
        Q.push_back({l[i], i, v[i]});
        Q.push_back({r[i] + 1, i, 0});
    }
    sort(Q.begin(), Q.end(), [](update a, update b){
        return a.t < b.t;
    });
    int qid = 0;
    vector<int32_t> s(n);
    for(int i = 0; i < n; i++){
        while(qid < (int) Q.size() && Q[qid].t <= i) st_update(Q[qid].pos, Q[qid].val), qid++;
        int pos = st_position(c[i]); pos = max(0LL, pos - 1);
        s[i] = f(node(a[pos++]), s[i], c[i]);
        s[i] = f(st_suffix(pos), s[i], c[i]);
    }
    return s;
}

Subtask #1
0 / 3.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 38072 KB Output is correct
2 Correct 268 ms 41784 KB Output is correct
3 Correct 298 ms 41648 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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