| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 834608 | Mohmad_Zaid | 사탕 분배 (IOI21_candies) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "candies.h"
#include <bits/stdc++.h>
#define str string
#define loop(n) for (int i = 0; i < n; i++)
#define ld long double
#define ll long long
#define endl '\n'
#define pb push_back
#define vsort(vec) sort(vec.begin(), vec.end())
#define rev(a) reverse(a.begin(), a.end())
#define print(a) loop(a.size())cout<<a[i]<<' '
// #define int long long
const int mod = 1e9 + 7;
using namespace std;
int lcm(int a, int b) { return ((a * b) / __gcd(a, b)); }
ll binpow(ll base,ll exponent){
base%=mod;
ll res=1;
while(exponent){
if(exponent&1){
res=(res*base)%mod;
}
base=(base*base)%mod;
exponent>>=1;
}
return res;
}
struct segtree{
ll size=1;
vector<ll>arr;
void init(ll n){
while(size<n)size*=2;
arr.assign(2*size-1,0);
}
void update(ll l,ll r,ll x,ll lx,ll rx,ll v){
if(rx<=l || lx>=r)return;
if(lx>=l && rx<=r){
arr[x]+=v;
return;
}
ll mid=(lx+rx)/2;
update(l,r,2*x+1,lx,mid,v);
update(l,r,2*x+2,mid,rx,v);
}
void update(ll l,ll r,ll v){
update(l,r,0,0,size,v);
}
void get_ans(ll i,ll x,ll lx,ll rx,ll& ans){
if(lx>i || rx<=i)return;
if(lx<=i && rx>i){
ans+=arr[x];
}
ll mid=(lx+rx)/2;
if(i<mid)get_ans(i,2*x+1,lx,mid,ans);
else get_ans(i,2*x+2,mid,rx,ans);
}
void get_ans(ll i,ll& ans){
get_ans(i,0,0,size,ans);
}
};
vector<ll> distribute_candies(vector<ll> c, vector<ll> l,vector<ll> r, vector<ll> v) {
ll n = c.size();
ll q= l.size();
segtree st;
st.init(n);
vector<ll> s(n);
for(ll iter=0;iter<q;iter++){
st.update(l[iter],r[iter]+1,v[iter]);
}
for(ll i=0;i<n;i++){
ll v=0;
st.get_ans(i,v);
s[i]=min(c[i],v);
}
return s;
}