Submission #1243752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243752		alexaaa	Distributing Candies (IOI21_candies)	C++20	0 / 100	5093 ms	13636 KiB

candies

#include<iostream>
#include<vector>
#include<map>
using namespace std;

vector<long long> st(900000);



long long query(int node, int r_begin, int r_end, int l , int r){
    // propagate(node, r_begin, r_end);

    if(r_begin > r || r_end < l){
        return 0;
    }
    else if(r_begin >= l && r_end <= r){
        return st[node];
    }
    int mid = (r_begin + r_end)/2;
    return query(2*node,r_begin,mid,l,r) + query(2*node+1,mid+1,r_end,l,r);

}
void add(int node, int r_begin, int r_end, int l, int r, int v, int c_i){
    if (r_begin > r || r_end < l) return;

    if (r_begin == r_end) { // leaf node
        if (r_begin >= l && r_begin <= r) {
            if (v > 0)
                st[node] = min((long long)c_i, st[node] + (long long)v);
            else
                st[node] = max((long long)0, st[node] + (long long)v);
        }
        return;
    }

    int mid = (r_begin + r_end) / 2;
    add(2 * node, r_begin, mid, l, r, v, c_i);
    add(2 * node + 1, mid + 1, r_end, l, r, v, c_i);
    st[node] = st[2 * node] + st[2 * node + 1];
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){
    vector<int> answer;
    int c_i = c[0];
    for(int i = 0;i < l.size(); i++){
        add(1,0,c.size()-1,l[i],r[i],v[i],c_i);
    }
    for(int i = 0; i < c.size(); i++){
        long long num = query(1,0,c.size()-1,i,i);
        answer.push_back((int)num);
    }
    return answer;

    
}

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