#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
int binarysearch(int sum,int n ,vector<pair<int,pair<int,int>>>crr){
int left = 0;
int right = n-1;
while(left<=right){
int mid = left + right >>1;
if (sum+crr[mid].second.first>=crr[mid].first){
left = mid + 1;
}
else right = mid - 1;
}
return min(left,n-1);
}
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();
vector<int>ans(n,0);
vector<pair<int,pair<int,int>>>crr;
for (int i =0;i<n;++i){
crr.push_back({c[i],{0,i}});
}
sort(crr.begin(),crr.end(),[&](pair<int,pair<int,int>>a,pair<int,pair<int,int>>b){
return a.first<b.first;
});
for (int i =0;i<l.size();){
int sum=0;
while(i<l.size()&&v[i]>0){
sum+=v[i];++i;
}
if (sum!=0){
int temp = binarysearch(sum,n,crr);
crr[0].second.first=crr[temp].first;
}
else {
int mi =0;
while(i<l.size()&&v[i]<=0){
mi+=v[i];
++i;
}
int temp = binarysearch(abs(mi),n,crr);
int temp2=crr[0].second.first+mi;
crr[0].second.first=0;
crr[temp].second.first=temp2;
}
}
vector<int>prr(n,0);
prr[0]=crr[0].second.first;
for (int i =1;i<n;++i){
prr[i]=(crr[i].second.first+crr[i-1].second.first)-(crr[n-1].first-crr[i].first);
prr[i]+=prr[i-1];
}
for (int i =0;i<n;++i){
ans[crr[i].second.second]=max(0,min(prr[i],crr[i].first));
}
return ans;*/
int n = c.size();
vector<int>ans(n,0);
vector<int64_t>pref(n+1,0);
for (int i =0;i<l.size();++i){
if (v[i]>0){
pref[l[i]]+=v[i];
pref[r[i]+1]-=v[i];
}
else {
for(int j = 1;j<n;++j){
pref[j]+=pref[j-1];
pref[j-1]=min(pref[j-1],(int64_t)c[j-1]);
if (l[i]<=j-1&&r[i]>=j-1){
pref[j-1]=max((int64_t)pref[j-1]+v[i],(int64_t)0);
}
}
pref[n-1]=min(pref[n-1],(int64_t)c[n-1]);
if (l[i]<=n-1&&r[i]>=n-1){
pref[n-1]=max((int64_t)pref[n-1]+v[i],(int64_t)0);
}
}
}
ans[0]=min(pref[0],(int64_t)c[0]);
for (int i =1;i<n;++i){
pref[i]+=pref[i-1];
ans[i]=max((int64_t)0,(int64_t)min(pref[i],(int64_t)c[i]));
}
return ans;
}
int main() {
int n;
assert(1 == scanf("%d", &n));
std::vector<int> c(n);
for(int i = 0; i < n; ++i) {
assert(scanf("%d", &c[i]) == 1);
}
int q;
assert(1 == scanf("%d", &q));
std::vector<int> l(q), r(q), v(q);
for(int i = 0; i < q; ++i) {
assert(scanf("%d %d %d", &l[i], &r[i], &v[i]) == 3);
}
std::vector<int> ans = distribute_candies(c, l, r, v);
for(int i = 0; i < n; ++i) {
if (i > 0) {
printf(" ");
}
printf("%d", ans[i]);
}
printf("\n");
fclose(stdout);
return 0;
}
Compilation message
candies.cpp: In function 'int binarysearch(int, int, std::vector<std::pair<int, std::pair<int, int> > >)':
candies.cpp:9:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
9 | int mid = left + right >>1;
| ~~~~~^~~~~~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:70:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for (int i =0;i<l.size();++i){
| ~^~~~~~~~~
/usr/bin/ld: /tmp/ccf2K485.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccqrd5M3.o:candies.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
