#include "candies.h"
#include <bits/stdc++.h>
#define vi vector<int>
#define sz(x) (x).size()
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define pii pair<int, int>
#define vpii vector<pii>
#define pb push_back
using namespace std;
////cout
const int N=1000006, INF=1e9 + 7;
int n, q, lazy[4*N];
//struct aaa{int mx, mn, mxi, mni;} T[4*N], o={0,INF,-1,-1};
pair<pii,pii> T[4*N], o={{0, -1}, {INF, -1}};
void push(int x){
lazy[x<<1 ]+=lazy[x];
lazy[x<<1|1]+=lazy[x];
T[x].F.F+=lazy[x];
T[x].S.F+=lazy[x];
lazy[x]=0;
}
void build(int L=0, int R=n, int x=1){
if(L==R){
T[x]={{0, L}, {0, L}};
return;
}
int m=L+R>>1;
build(L, m, x<<1);
build(m+1, R, x<<1|1);
auto xl=T[x<<1], xr=T[x<<1|1];
T[x]={max(xl.F, xr.F), min(xl.S, xr.S)};
}
void upd(int l, int r, int val, int L=0, int R=n, int x=1){
if(R<l || L>r)return;
if(L>=l && R<=r){
lazy[x]+=val;
return;
}
int m=L+R>>1;
push(x);
upd(l, r, val, L, m, x<<1);
upd(l, r, val, m+1, R, x<<1|1);
push(x<<1); push(x<<1|1);
auto xl=T[x<<1], xr=T[x<<1|1];
T[x]={max(xl.F, xr.F), min(xl.S, xr.S)};
}
pair<pii,pii> getmaxmin(int l, int r, int L=0, int R=n, int x=1){
if(R<l || L>r)return o;
push(x);
if(L>=l && R<=r){
return T[x];
}
int m=L+R>>1;
auto [mx1, mn1] = getmaxmin(l, r, L, m, x<<1);
auto [mx2, mn2] = getmaxmin(l, r, m+1, R, x<<1|1);
return {max(mx1, mx2), min(mn1, mn2)};
}
int get(int i, int L=0, int R=n, int x=1){
push(x);
if(L==R)return T[x].F.F;
int m=L+R>>1;
if(m>=i){
return get(i, L, m, x<<1);
}else{
return get(i, m+1, R, x<<1|1);
}
}
int solve(int c){
int l=0, r=n, d, u, dval, uval;
while(l<=r){
for (int i=0; i<=n; i++){
pair<pii,pii> y=getmaxmin(i, i);
//cout<<i<<" "<<get(i)<<" "<<y.F.F<<" "<<y.F.S<<" "<<y.S.F<<" "<<y.S.S<<endl;
}//cout<<endl;
int m=l+r>>1;
auto [mx,mn] = getmaxmin(m, n);
//cout<<"AAA"<<m<<" "<<mx.F<<" "<<mx.S<<" "<<mn.F<<" "<<mn.S<<endl;
if(mx.F-mn.F<c)r=m-1;
else{
dval=mn.F; d=mn.S;
uval=mx.F; u=mx.S;
l=m+1;
}
}
//cout<<d<<" "<<u<<endl;
if(d<u){
return c-(get(u)-get(n));
}else{
return get(n)-get(d);
}
}
vi distribute_candies(vi c, vi l, vi r, vi v) {
n = sz(c), q=sz(l);
vi ans(n);
vpii a[n+1];
build();
for (int i=0; i<q; i++){
a[l[i] ].pb({v[i],i});
a[r[i]+1].pb({v[i],i});
}
set<pii> s;
for (int i=0; i<n; i++){
for (auto [val,t]:a[i]){
if(s.find({val,t})!=s.end()){
s.erase({val,t});
upd(t+1, n, -val);
}else{
s.insert({val,t});
upd(t+1, n, val);
}
}
ans[i]=solve(c[i]);
}
return ans;
}
Compilation message
candies.cpp: In function 'void build(int, int, int)':
candies.cpp:34:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
34 | int m=L+R>>1;
| ~^~
candies.cpp: In function 'void upd(int, int, int, int, int, int)':
candies.cpp:47:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | int m=L+R>>1;
| ~^~
candies.cpp: In function 'std::pair<std::pair<int, int>, std::pair<int, int> > getmaxmin(int, int, int, int, int)':
candies.cpp:63:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
63 | int m=L+R>>1;
| ~^~
candies.cpp: In function 'int get(int, int, int, int)':
candies.cpp:72:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
72 | int m=L+R>>1;
| ~^~
candies.cpp: In function 'int solve(int)':
candies.cpp:87:27: warning: variable 'y' set but not used [-Wunused-but-set-variable]
87 | pair<pii,pii> y=getmaxmin(i, i);
| ^
candies.cpp:91:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
91 | int m=l+r>>1;
| ~^~
candies.cpp:81:25: warning: variable 'dval' set but not used [-Wunused-but-set-variable]
81 | int l=0, r=n, d, u, dval, uval;
| ^~~~
candies.cpp:81:31: warning: variable 'uval' set but not used [-Wunused-but-set-variable]
81 | int l=0, r=n, d, u, dval, uval;
| ^~~~
candies.cpp:73:5: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
73 | if(m>=i){
| ^~
candies.cpp:81:22: note: 'u' was declared here
81 | int l=0, r=n, d, u, dval, uval;
| ^
candies.cpp:73:5: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
73 | if(m>=i){
| ^~
candies.cpp:81:19: note: 'd' was declared here
81 | int l=0, r=n, d, u, dval, uval;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
308 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5078 ms |
36256 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1130 ms |
456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
308 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
