#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#include "candies.h"
#include <vector>
llo cur[200001];
llo tree[4*200001];
llo tree2[4*200001];
void update(llo no,llo l,llo r,llo i,llo j){
if(l==r){
tree[no]=j;
}
else{
llo mid=(l+r)/2;
if(i<=mid){
update(no*2+1,l,mid,i,j);
}
else{
update(no*2+2,mid+1,r,i,j);
}
tree[no]=max(tree[no*2+1],tree[no*2+2]);
}
}
void update2(llo no,llo l,llo r,llo i,llo j){
if(l==r){
tree2[no]=j;
}
else{
llo mid=(l+r)/2;
if(i<=mid){
update2(no*2+1,l,mid,i,j);
}
else{
update2(no*2+2,mid+1,r,i,j);
}
tree2[no]=max(tree2[no*2+1],tree2[no*2+2]);
}
}
llo query2(llo no,llo l,llo r,llo aa,llo bb){
if(r<aa or l>bb){
return -1;
}
if(aa<=l and r<=bb){
return tree[no];
}
llo mid=(l+r)/2;
return max(query2(no*2+1,l,mid,aa,bb),query2(no*2+2,mid+1,r,aa,bb));
}
llo query3(llo no,llo l,llo r,llo aa,llo bb){
if(r<aa or l>bb){
return -1;
}
if(aa<=l and r<=bb){
return tree2[no];
}
llo mid=(l+r)/2;
return max(query3(no*2+1,l,mid,aa,bb),query3(no*2+2,mid+1,r,aa,bb));
}
llo val2[2000001];
llo pre[2000001];
llo cot=-1;
vector<pair<llo,llo>> ss;
llo n;
llo query(llo ind){
llo x=query2(0,0,n-1,ind,n-1);
llo y=query3(0,0,n-1,ind,n-1);
llo z;
if(x<=y){
z=0;
}
else{
z=ss[ind].a;
}
//cout<<ind<<":"<<x<<":"<<y<<":"<<z<<endl;
z+=pre[cot]-pre[max(x,y)+1];
return z;
}
//llo lazy2[]
/*void u(llo i,llo j){
while(i<=200000){
tree[i]+=j;
i+=(i&-i);
}
}
llo ss(llo i){
llo su=0;
while(i>0){
su+=tree[i];
i-=(i&-i);
}
return su;
}*/
std::vector<int> distribute_candies(vector<int> it,vector<int> ll,
vector<int> rr,vector<int> aa) {
pre[0]=0;
for(llo i=1;i<=aa.size();i++){
pre[i]=pre[i-1]+aa[i-1];
}
/* for(int i=0;i<=aa.size();i++){
cout<<pre[i]<<":";
}
cout<<endl;*/
n=it.size();
llo q=ll.size();
for(llo i=0;i<n;i++){
cur[i]=0;
}
for(llo i=0;i<4*n;i++){
tree[i]=-1;
}
for(llo i=0;i<4*n;i++){
tree2[i]=-1;
}
for(llo i=0;i<n;i++){
ss.pb({it[i],i});
}
sort(ss.begin(),ss.end());
for(llo i=0;i<q;i++){
cot=i;
/*for(int j=0;j<n;j++){
cout<<query(j)<<":";
}
cout<<endl;*/
if(aa[i]>0){
llo low=-1;
for(llo j=19;j>=0;j--){
if(low+(1<<j)<n){
llo ind=low+(1<<j);
llo xx=query(ind);
//cout<<low<<":"<<xx<<endl;
if(xx+aa[i]>=ss[ind].a){
low=ind;
}
}
}
/*if(low+1<n){
update(0,0,n-1,low+1,n,aa[i]);
}*/
if(low>=0){
//set to max val
update(0,0,n-1,low,i);
}
//cout<<low<<":"<<endl;
}
else{
llo low=-1;
for(llo j=19;j>=0;j--){
if(low+(1<<j)<n){
llo ind=low+(1<<j);
llo xx=query(ind);
if(xx+aa[i]<0){
low=ind;
}
}
}
/* if(low+1<n){
update(0,0,n-1,low+1,n,aa[i]);
}*/
if(low>=0){
//set to 0
//set to max val
update2(0,0,n-1,low,i);
}
//cout<<low<<":"<<endl;
}
//u(ll[i]+1,aa[i]);
//u(rr[i]+2,-aa[i]);
/*for(llo j=ll[i];j<=rr[i];j++){
cur[j]+=aa[i];
cur[j]=max(cur[j],0);
cur[j]=min(cur[j],it[j]);
}*/
}
vector<int> ans;
for(llo i=0;i<n;i++){
ans.pb(0);
}
cot=q;
for(llo i=0;i<n;i++){
ans[ss[i].b]=query(i);
//ans.pb((llo)min((llo)it[i],ss(i+1)));
//cout<<ss(i+1)<<":";
}
//cout<<endl;
return ans;
}
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:111:18: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for(llo i=1;i<=aa.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 |
740 ms |
27212 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 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
605 ms |
6816 KB |
Output is correct |
| 4 |
Correct |
195 ms |
21148 KB |
Output is correct |
| 5 |
Correct |
1990 ms |
27180 KB |
Output is correct |
| 6 |
Correct |
2027 ms |
27164 KB |
Output is correct |
| 7 |
Correct |
1931 ms |
27164 KB |
Output is correct |
| 8 |
Correct |
2086 ms |
27184 KB |
Output is correct |
| 9 |
Correct |
1629 ms |
27168 KB |
Output is correct |
| # |
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 |
- |
