#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = 200005;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi;
struct node {
int s,e,m,lazy;
pi val,mn,mx;
node *l, *r;
node(int _s, int _e){
s=_s;e=_e;m=(s+e)/2;
lazy=0;
val=mn={0,s};
mx={0,-s};
if(s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void value(){
if(lazy==0)return;
if(s==e){
mn.first+=lazy;
mx.first+=lazy;
val.first+=lazy;
lazy=0;
return ;
}
val.first+=lazy;
mn.first+=lazy;
mx.first+=lazy;
l->lazy+=lazy;
r->lazy+=lazy;
lazy=0;
return;
}
void update(int x, int y, int nval){
value();
if(s==x&&e==y){
lazy+=nval;
return;
}
if(x>m)r->update(x,y,nval);
else if(y<=m)l->update(x,y,nval);
else l->update(x,m,nval),r->update(m+1,y,nval);
l->value(),r->value();
mn=min(l->mn,r->mn);
mx=max(l->mx,r->mx);
}
int query(int x, int y){
value();
if(s==x&&e==y)return val.first;
if(x>m)return r->query(x,y);
else if(y<=m)return l->query(x,y);
else return l->query(x,m) + query(m+1,y);
}
pi query_max(int x, int y){
value();
if(s==x&&e==y)return mx;
if(x>m)return r->query_max(x,y);
else if(y<=m)return l->query_max(x,y);
else return max(l->query_max(x,m), r->query_max(m+1,y));
}
pi query_min(int x, int y){
value();
if(s==x&&e==y)return mn;
if(x>m)return r->query_min(x,y);
else if(y<=m)return l->query_min(x,y);
else return min(l->query_min(x,m), r->query_min(m+1,y));
}
}*seg;
vector<int32_t> distribute_candies(vector<int32_t> c, vector<int32_t> l,
vector<int32_t> r, vector<int32_t> v) {
int n=c.size();
vector<pi> A[n+5];
int Q=l.size();
seg=new node(0,Q+3); // 0 is just set to 0 for everything
for(int t=0;t<Q;t++){
A[l[t]].push_back({v[t],t+1});
A[r[t]+1].push_back({-v[t],t+1});
}
vector<int32_t>res;
for(int i=0;i<=n-1;i++){
//debug(i);
for(auto x:A[i]){
//debug(x.first,x.second);
seg->update(x.second,Q+3,x.first);
}
int lo=0,hi=Q+2;
while(lo<hi-1){
int mi=(lo+hi)/2;
pi MX=seg->query_max(mi,Q+3);
MX.second*=-1;
pi MN=seg->query_min(mi,Q+3);
//debug(MX.first,MN.first,c[i]);
if(MX.first-MN.first>=c[i]){
lo=mi;
} else{
hi=mi;
}
}
pi MN=seg->query_min(lo,Q+3);
pi MX=seg->query_max(lo,Q+3);
MX.second*=-1;
int F=seg->query(Q+3,Q+3);
//debug(MN.first,MN.second,MX.first,MX.second,F);
if(MN.second>=MX.second){
res.push_back(F-MN.first);
} else {
res.push_back(c[i]+(F-MX.first));
}
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1010 ms |
71732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
