| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 834604 | Mohmad_Zaid | Distributing Candies (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{
int size=1;
vector<int>arr;
void init(int n){
while(size<n)size*=2;
arr.assign(2*size-1,0);
}
void update(int l,int r,int x,int lx,int rx,int v){
if(rx<=l || lx>=r)return;
if(lx>=l && rx<=r){
arr[x]+=v;
return;
}
int mid=(lx+rx)/2;
update(l,r,2*x+1,lx,mid,v);
update(l,r,2*x+2,mid,rx,v);
}
void update(int l,int r,int v){
update(l,r,0,0,size,v);
}
void get_ans(int i,int x,int lx,int rx,int& ans){
if(lx>i || rx<=i)return;
if(lx<=i && rx>i){
ans+=arr[x];
}
int 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(int i,int& ans){
get_ans(i,0,0,size,ans);
}
};
vector<int> distribute_candies(vector<int> c, vector<int> l,vector<int> r, vector<int> v) {
int n = c.size();
int q= l.size();
segtree st;
st.init(n);
vector<int> s(n);
for(int iter=0;iter<q;iter++){
st.update(l[iter],r[iter]+1,v[iter]);
}
for(int i=0;i<n;i++){
int v=0;
st.get_ans(i,v);
s[i]=min(c[i],v);
}
return s;
}