# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
545852 | fuad27 | Fountain Parks (IOI21_parks) | 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>
using namespace std;
const int MAXN = 200'010;
long long fen[MAXN];
void upd(int at, long long val) {
at++;
while(at < MAXN) {
fen[at]+=val;
at+=at&(-at);
}
}
long long query(int r) {
long long sum = 0;
r++;
while(r > 0) {
sum+=fen[r];
r-=r&(-r);
}
return sum;
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n = c.size();
vector<int> s(n);
for(int i = 0;i<MAXN;i++)fen[i] =0;
for(int i = 0;i<n;i++) {
upd(l[i], v[i]);
upd(r[i]+1, -v[i]);
}
for(int i = 0;i<n;i++) {
s[i] = max((long long)c[i], query(i));
}
return s;
}