제출 #1243230

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1243230		pcp	사탕 분배 (IOI21_candies)	C++20	8 / 100	119 ms	14060 KiB

candies

#include "candies.h"

#include <vector>
#include <cstring>

#define ll long long

using namespace std;


const int N=200050;

ll tree[4*N];


void updt(int node, int l, int r, int x, int y, int v){

    int m = (l + r) / 2;

    if (l > y || r < x)return;

    if (l  >= x && r <=y){

        tree[node]+=v;
        return;
    }

    if (y>m)updt(node*2+1, m+1, r, x, y, v);
    if (x<=m)updt(node*2, l, m, x, y, v);
}


ll candies(int node, int l, int r, int num){

    int m = (l + r)/2;

    if (l==r)return tree[node];

    if (num>m)return tree[node] + candies(node*2+1,m+1,r,num);
    return tree[node] + candies(node*2,l,m,num);
}





std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) 
    {



    int n = c.size();
    memset(tree, 0, sizeof tree);

    for (int i = 0; i < l.size();++i)updt(1,0,n-1,l[i],r[i],v[i]);
    
    vector<int> rem;
    for (int i = 0; i < n;++i){

        ll a =candies(1,0,n-1,i);
        ll b = c[i];
        rem.push_back(min(a, b));

    }

    return rem;

}

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