/**
* Prof.Nicola
**/
#include <bits/stdc++.h>
#include "candies.h"
using namespace std;
#define endl "\n"
#define mp make_pair
#define F first
#define S second
#define REP(i,l,r) for(long long i=(l);i<(r);i++)
#define PER(i,l,r) for(long long i=(r)-1;i>=(l);i--)
const long dx[4]={1,0,-1,0},dz[4]={0,1,0,-1};
const long double pi=3.14159265359;
const long long mod=1e9+7;
long long p(long long x){while(x&(x-1)){x=x&(x-1);}return x;}
template<class T>void re(T&x){cin>>x;}
template<class T1,class T2> void re(pair<T1,T2>&x){re(x.first);re(x.second);}
template<class T>void re(vector<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}}
template<class T>void re(deque<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}}
template<class T>void out(T x){cout<<x<<" ";}
template<class T1,class T2>void out(pair<T1,T2>x){out(x.first);out(x.second);cout<<endl;}
template<class T>void out(vector<T>x,long l=0,long r=0){if(!r){r=x.size();}for(long i=l;i<r;i++){out(x[i]);}cout<<endl;}
template<class T>void out(deque<T>x,long l=0,long r=0){if(!r){r=x.size();}for(long i=l;i<r;i++){out(x[i]);}cout<<endl;}
template<class T>T cross(complex<T>x,complex<T>z){return (conj(x)*z).imag();}
template<class T>T dot(complex<T>x,complex<T>z){return (conj(x)*z).real();}
long q;
struct segment_tree1
{
vector<long long>tree;
long long operation(long long x,long long z)
{
return max(x,z);
}
void build(vector<long long>v)
{
tree.clear();
long long x=v.size();
while(x&(x-1)){
x=x&(x-1);
}
if(v.size()!=x){
x*=2;
}
tree.resize(x*2);
tree[0]=x;
for(long i=0;i<v.size();i++){
tree[i+x]=v[i];
}
for(long i=x-1;i>0;i--){
tree[i]=operation(tree[i*2],tree[(i*2)+1]);
}
}
long long get(long long l,long long r)
{
l+=tree[0];
r+=tree[0];
long long ans=0;
while(l<=r){
if(l%2==1){
ans=operation(ans,tree[l]);
}
if(r%2==0){
ans=operation(ans,tree[r]);
}
l++;
l/=2;
r--;
r/=2;
}
return ans;
}
void update(long long x,long long z)
{
x+=tree[0];
tree[x]=z;
x/=2;
while(x>0){
tree[x]=operation(tree[x*2],tree[(x*2)+1]);
x/=2;
}
}
};
struct segment_tree2
{
vector<long long>tree;
long long operation(long long x,long long z)
{
return min(x,z);
}
void build(vector<long long>v)
{
tree.clear();
long long x=v.size();
while(x&(x-1)){
x=x&(x-1);
}
if(v.size()!=x){
x*=2;
}
tree.resize(x*2);
tree[0]=x;
for(long i=0;i<v.size();i++){
tree[i+x]=v[i];
}
for(long i=x-1;i>0;i--){
tree[i]=operation(tree[i*2],tree[(i*2)+1]);
}
}
long long get(long long l,long long r)
{
l+=tree[0];
r+=tree[0];
long long ans=1e9;
while(l<=r){
if(l%2==1){
ans=operation(ans,tree[l]);
}
if(r%2==0){
ans=operation(ans,tree[r]);
}
l++;
l/=2;
r--;
r/=2;
}
return ans;
}
void update(long long x,long long z)
{
x+=tree[0];
tree[x]=z;
x/=2;
while(x>0){
tree[x]=operation(tree[x*2],tree[(x*2)+1]);
x/=2;
}
}
};
segment_tree1 a;
segment_tree2 b;
long mx(long x)
{
long l=x,r=q-1,mid;
while(l<r){
mid=(l+r)/2;
if(a.get(l,mid)<=a.get(mid+1,r)){
l=mid+1;
}
else{
r=mid;
}
}
return l;
}
long mn(long x)
{
long l=x,r=q-1,mid;
while(l<r){
mid=(l+r)/2;
if(b.get(l,mid)>=b.get(mid+1,r)){
l=mid+1;
}
else{
r=mid;
}
}
return l;
}
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();
q=v.size();
std::vector<int> s(n);
long long now=0,sub=0,p1,p2,x=0;
vector<pair<long long,long> >srtd(n);
REP(i,0,n){
srtd[i]=mp(c[i],i);
}
sort(srtd.rbegin(),srtd.rend());
vector<long long>sum(q);
REP(i,0,q){
x+=v[i];
x=min(x,(long long)srtd[0].first);
x=max(0ll,x);
sum[i]=x;
}
a.build(sum);
b.build(sum);
x=0;
while(now<n&&x<q){
while(now<n&&x<q){
p1=mx(x);
p2=mn(p1);
while(now<n&&sum[p1]-sub<=srtd[now].first){
s[srtd[now].second]=sum[q-1]-sub;
now++;
}
if(now>=n){
break;
}
sub+=min(sum[p1]-sub-c[now],sum[p2]-sub);
if(sum[p2]-sub==0){
x=p2+1;
}
else{
break;
}
}
if(now<n){
s[srtd[now].second]=sum[q-1]-sub;
}
now++;
}
return s;
}
Compilation message
candies.cpp: In member function 'void segment_tree1::build(std::vector<long long int>)':
candies.cpp:42:20: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
42 | if(v.size()!=x){
| ~~~~~~~~^~~
candies.cpp:47:23: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(long i=0;i<v.size();i++){
| ~^~~~~~~~~
candies.cpp: In member function 'void segment_tree2::build(std::vector<long long int>)':
candies.cpp:98:20: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
98 | if(v.size()!=x){
| ~~~~~~~~^~~
candies.cpp:103:23: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(long i=0;i<v.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
159 ms |
21832 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 |
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 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
