#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
typedef long long int lld;
#define INF 1000000000000000000LL
lld arr[1000000];
struct f{
lld A; lld B; lld C;
};
f nest(f alpha, f beta){
return f{min(alpha.A,max(beta.A+alpha.C,alpha.B)),max(beta.B+alpha.C,alpha.B),alpha.C+beta.C};
}
/*
f max(f a, f b){
};
f in(f a, f b){
};
f operator +(f a, f b){
};
struct g{
f A,B,C;
};*/
class ST{
f lazy[1000000];
public:
void build(int a, int b, int node){
lazy[node]=f{INF,-INF,0};
if(a==b)return;
int mid=(a+b)/2;
build(a,mid,2*node);
build(mid+1,b,2*node+1);
}
void propag(int a, int b, int node){
lazy[2*node]=nest(lazy[node],lazy[2*node]);
lazy[2*node+1]=nest(lazy[node],lazy[2*node+1]);
lazy[node]=f{INF,-INF,0};
}
void update(int a, int b, int node, int x, int y, f operation){
if(b<x || y<a)return;
if(x<=a && b<=y){
lazy[node]=nest(operation,lazy[node]);
return;
}
propag(a,b,node);
int mid=(a+b)/2;
update(a,mid,2*node,x,y,operation);
update(mid+1,b,2*node+1,x,y,operation);
}
lld query(int a, int b, int node, int pos){
if(pos<=a && b<=pos){
return min(lazy[node].A,max(lazy[node].B,lazy[node].C));
}
propag(a,b,node);
int mid=(a+b)/2;
if(mid<pos)return query(mid+1,b,2*node+1,pos);
if(mid>=pos)return query(a,mid,2*node,pos);
}
f query2(int a, int b, int node, int pos){
if(pos<=a && b<=pos){
return lazy[node];
}
propag(a,b,node);
int mid=(a+b)/2;
if(mid<pos)return query2(mid+1,b,2*node+1,pos);
if(mid>=pos)return query2(a,mid,2*node,pos);
}
void print(int a, int b, int node){
cout<<a<<" "<<b<<" "<<node<<" "<<lazy[node].A<<" "<<lazy[node].B<<" "<<lazy[node].C<<endl;
if(a==b)return;
int mid=(a+b)/2;
print(a,mid,2*node);
print(mid+1,b,2*node+1);
}
};
ST S;
vector<int> a,b;
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();
std::vector<int> s(n);
/*if(n<=2000 && l.size()<=2000){
rep(i,0,n)arr[i]=0;
rep(q,0,l.size()){
rep(i,l[q],r[q]+1){
if(v[q]>0){
arr[i]=min(arr[i]+v[q],(lld)c[i]);
}else{
arr[i]=max(arr[i]+v[q],0LL);
}
}
}
rep(i,0,n)s[i]=arr[i];
return s;
}*/
/*rep(i,0,n+1)arr[i]=0;
rep(i,0,l.size()){
arr[l[i]]+=v[i];
arr[r[i]+1]-=v[i];
}
rep(i,1,n)arr[i]=arr[i]+(arr[i-1]);
rep(i,0,n){
s[i]=min(arr[i],(lld)c[i]);
}*/
a.resize(n);
b.resize(n);
S.build(0,l.size(),1);
S.update(0,l.size(),1,0,0,f{INF,0,-INF});
rep(i,1,l.size()+1){
//S.print(0,n-1,1);
if(v[i-1]>0){
S.update(0,l.size(),1,0,i-1,f{INF,-INF,v[i-1]});
S.update(0,l.size(),1,i,i,f{INF,-INF,0});
}
if(v[i-1]<0){
S.update(0,l.size(),1,0,i,f{INF,-INF,v[i-1]});
S.update(0,l.size(),1,0,i,f{INF,0,0});
}
//S.print(0,l.size(),1);
}
vector<pair<lld,lld> >V;
rep(i,0,l.size()+1){
if(i==0 || v[i-1]>0){
//cout<<S.query2(0,l.size(),1,i).B<<" "<<S.query2(0,l.size(),1,i).C<<endl;
V.push_back({S.query2(0,l.size(),1,i).B,S.query2(0,l.size(),1,i).C});
}
}
//rep(i,0,V.size())cout<<V[i].first<<" "<<V[i].second<<endl;
sort(V.begin(),V.end());
vector<pair<lld,lld> >V2;
V2.push_back(V[0]);
rep(i,1,V.size()){
if(V[i].second<V2[V2.size()-1].second){
V2.push_back(V[i]);
}
}
//rep(i,0,V2.size())cout<<V2[i].first<<" "<<V2[i].second<<endl;
rep(i,0,n){
int lo=0;
int hi=V2.size()-1;
while(hi-lo>1){
int mid=(hi+lo)/2;
if(V2[mid].first<V2[mid].second+c[i]){
lo=mid;
}else hi=mid;
}
//cout<<max(V2[lo].first,V2[lo].second+c[i])<<" "<<max(V2[hi].first,V2[hi].second+c[i])<<endl;
s[i]=min(max(V2[lo].first,V2[lo].second+c[i]),max(V2[hi].first,V2[hi].second+c[i]));
}
return s;
}
Compilation message
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:5:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define rep(i,a,b) for(int i=a;i<b;i++)
......
115 | rep(i,1,l.size()+1){
| ~~~~~~~~~~~~~~
candies.cpp:115:5: note: in expansion of macro 'rep'
115 | rep(i,1,l.size()+1){
| ^~~
candies.cpp:5:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define rep(i,a,b) for(int i=a;i<b;i++)
......
128 | rep(i,0,l.size()+1){
| ~~~~~~~~~~~~~~
candies.cpp:128:5: note: in expansion of macro 'rep'
128 | rep(i,0,l.size()+1){
| ^~~
candies.cpp:5:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define rep(i,a,b) for(int i=a;i<b;i++)
......
138 | rep(i,1,V.size()){
| ~~~~~~~~~~~~
candies.cpp:138:2: note: in expansion of macro 'rep'
138 | rep(i,1,V.size()){
| ^~~
candies.cpp: In member function 'f ST::query2(int, int, int, int)':
candies.cpp:73:2: warning: control reaches end of non-void function [-Wreturn-type]
73 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
327 ms |
25440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
238 ms |
19420 KB |
Output is correct |
| 4 |
Correct |
61 ms |
4400 KB |
Output is correct |
| 5 |
Correct |
292 ms |
23476 KB |
Output is correct |
| 6 |
Correct |
293 ms |
24888 KB |
Output is correct |
| 7 |
Correct |
305 ms |
25004 KB |
Output is correct |
| 8 |
Correct |
290 ms |
24888 KB |
Output is correct |
| 9 |
Correct |
327 ms |
26968 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
