Submission #1025737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025737		HappyCapybara	Distributing Candies (IOI21_candies)	C++17	8 / 100	149 ms	17744 KiB

candies

#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;
}

• Subtask 1: 0 / 3
• Subtask 2: 8 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33