#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);
}
const int MXN = 1e6;
vector<pair<int,int>>tree(4*MXN);
int arr[MXN];
int lazy[MXN];
int func(int a,int b){
return min(a,b);//sum
}
void add(pair<int,int>&a,pair<int,int>b,pair<int,int>c){
a.second = max(a.second,b.second+c.second);
a.first = min(a.first+b.first+c.first,a.second);
}
void ad(pair<int,int>&a,int b){
a.first = min(a.second,a.first+b);
}
void build(vector<int>arr,int node,int node_low,int node_high){
if (node_low==node_high){
tree[node].second=arr[node_low];
}
else {
int mid =(node_low+node_high)>>1;
build(arr,node*2,node_low,mid);
build(arr,node*2 + 1,mid+1,node_high);
add(tree[node],tree[node*2],tree[node*2 + 1]);
}
}
void update(int node,int node_low,int node_high,int q_low,int q_high,int new_val){
if (lazy[node]!=0){
ad(tree[node],(node_high - node_low +1 )*lazy[node]);
if (node_low!=node_high){
lazy[node*2]+=lazy[node];
lazy[node*2 + 1]+=lazy[node];
}
lazy[node]=0;
}
if (node_low>node_high||node_low>q_high||node_high<q_low)return;
if (q_low<=node_low&&q_high>=node_high){
ad(tree[node],(node_high - node_low + 1)*new_val);
if (node_low!=node_high){
lazy[node*2]+=new_val;
lazy[node*2 + 1]+=new_val;
}
return ;
}
int mid = (node_low + node_high)/2;
update(node*2,node_low,mid,q_low,q_high,new_val);
update(node*2 + 1,mid + 1,node_high,q_low,q_high,new_val);
add(tree[node],tree[node*2],tree[node*2 + 1]);
}
int query(int node,int node_low,int node_high,int query_low,int query_high){
if (node_low>node_high||node_low>query_high||node_high<query_low)return INT_MAX;
if (lazy[node]!=0){
ad(tree[node],(node_high - node_low + 1)*lazy[node]);
if (node_low!=node_high){
lazy[node*2]+=lazy[node];
lazy[node*2 + 1]+=lazy[node];
}
lazy[node]=0;
}
if (query_low<=node_low&&query_high>=node_high){
return tree[node].first;
}
int mid = (node_low+node_high)/2;
return func(query(node*2,node_low,mid,query_low,query_high),query(node*2 + 1,mid+1,node_high,query_low,query_high));
}
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);
build(c,1,0,n-1);
for (int i =0;i<l.size();++i){
update(1,0,n-1,l[i],r[i],v[i]);
}
for (int i =0;i<n;++i){
ans[i]=query(1,0,n-1,i,i);
}
return ans;
}
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:139:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | for (int i =0;i<l.size();++i){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
31556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5087 ms |
54040 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
31692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
31616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
31556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
