Submission #1025737

# Submission time Handle Problem Language Result Execution time Memory
1025737 2024-07-17T09:28:55 Z HappyCapybara Distributing Candies (IOI21_candies) C++17
8 / 100
149 ms 17744 KB
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long

int n;
vector<ll> st;

void update(int pos, ll val, int node=1, int tl=0, int tr=n-1){
    if (tl == tr){
        st[node] += val;
        return;
    }
    int tm = (tl+tr)/2;
    if (pos <= tm) update(pos, val, node*2, tl, tm);
    else update(pos, val, node*2+1, tm+1, tr);
    st[node] = st[node*2]+st[node*2+1];
}

ll query(int l, int r, int node=1, int tl=0, int tr=n-1){
    if (l <= tl && tr <= r) return st[node];
    int tm = (tl+tr)/2;
    ll res = 0;
    if (l <= tm) res += query(l, r, node*2, tl, tm);
    if (tm+1 <= r) res += query(l, r, node*2+1, tm+1, tr);
    return res;
}
 
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){
    n = c.size();
    int q = l.size();
    st.resize(4*n, 0);
    for (int i=0; i<q; i++){
        update(l[i], v[i]);
        if (r[i] < n-1) update(r[i]+1, -v[i]);
    }
    vector<int> s(n);
    for (int i=0; i<n; i++) s[i] = min((ll) c[i], query(0, i));
    return s;
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 149 ms 13556 KB Output is correct
2 Correct 145 ms 17744 KB Output is correct
3 Correct 148 ms 17492 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -