Submission #570939

#	Time	Username	Problem	Language	Result	Execution time	Memory
570939		sff_user	Distributing Candies (IOI21_candies)	C++17	0 / 100	308 ms	25812 KiB

candies

#include <vector>
#include<bits/stdc++.h>

#define ll long long

using namespace std;


int N = 200005;
vector<ll> st(4 * N);
vector<ll> lazy(4 * N);
void build(int idx , int l , int r,vector<int>&s){
	if(l==r){
        s[l]=st[idx];
		return;
	}
    int mid = (l+r)/2;
	build(2*idx , l , mid,s);
	build(2*idx+1, mid+1 ,r,s);
}
 
 
void rUp(int idx, int l, int r, int i,int j, int v)
{
    if (lazy[idx] != 0)
    {
        st[idx] += (r - l + 1) * lazy[idx];
        if (l != r)
        {
            lazy[2 * idx] += lazy[idx];
            lazy[2 * idx + 1] += lazy[idx];
        }
        lazy[idx] = 0;
    }
 
    if (j < l || r < i)
        return;
 
    if (i <= l && r <= j)
    {
        st[idx] += (r - l + 1) * v;
        if (l != r)
        {
            lazy[2 * idx] += v;
            lazy[2 * idx + 1] += v;
        }
        return;
    }
 
    int mid = (l + r) / 2;
    rUp(idx * 2, l, mid, i,j, v);
    rUp(idx * 2 + 1, mid + 1, r, i,j, v);
    st[idx] = st[idx * 2] + st[idx * 2 + 1];
}




vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> v) {
    int n = c.size();
    int q = l.size();
    vector<int> s(n);
    for(int i = 0 ; i < q ; i ++){
        rUp(1,1,n,l[i],r[i],v[i]);
    }
    build(1,1,n,s);
    for(int i = 0 ; i < n ; i++) s[i] =min(s[i],c[i]);
    return s;
}

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