#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{0,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);
rep(i,0,n+1)arr[i]=0;
rep(i,0,l.size()){
arr[l[i]]+=v[i];
arr[r[i]+1]-=v[i];
}
s[0]=arr[0];
rep(i,1,n)s[i]=arr[i]+(s[i-1]);
rep(i,0,n){
s[i]=min(s[i],c[i]);
}
/*a.resize(n);
b.resize(n);
S.build(0,l.size()-1,1);
rep(i,0,l.size()){
//S.print(0,n-1,1);
if(v[i]>0){
S.update(0,l.size()-1,1,0,i-1,f{INF,-INF,v[i]});
S.update(0,l.size()-1,1,i,i,f{INF,-INF,0});
}
if(v[i]<0){
S.update(0,l.size()-1,1,0,i-1,f{INF,-INF,v[i]});
S.update(0,l.size()-1,1,0,i-1,f{INF,0,0});
}
//S.print(0,n-1,1);
}
vector<pair<lld,lld> >V;
rep(i,0,l.size()){
cout<<S.query2(0,l.size()-1,1,i).B<<" "<<S.query2(0,l.size()-1,1,i).C<<endl;
V.push_back({S.query2(0,l.size()-1,1,i).B,S.query2(0,l.size()-1,1,i).C});
}*/
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++)
......
89 | rep(i,0,l.size()){
| ~~~~~~~~~~~~
candies.cpp:89:5: note: in expansion of macro 'rep'
89 | rep(i,0,l.size()){
| ^~~
| # |
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 |
Incorrect |
127 ms |
8896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 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 |
- |
