#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
typedef int64_t i64;
#define VII vector<int>
struct seg{
int sz = 1;
vector<i64>mn,mx,op;
seg(int n){
while(sz < n) sz*=2;
mn.assign(sz*2,0ll);
mx.assign(sz*2,0ll);
op.assign(sz*2,0ll);
}
void update(int l,int r,i64 v,int x=0,int lx=0,int rx=-1){
if(rx == -1) rx = sz;
if(rx <= l || lx >= r) return;
if(rx <= r && lx >= l){
op[x] += v;
mx[x] += v;
mn[x] += v;
return;
}
int m = (lx+rx)/2;
update(l,r,v,x*2+1,lx,m);
update(l,r,v,x*2+2,m,rx);
mn[x] = min(mn[x*2+1],mn[x*2+2]) + op[x];
mx[x] = max(mx[x*2+1],mx[x*2+2]) + op[x];
}
i64 getmn(int l,int r,int x=0,int lx=0,int rx=-1){
if(rx == -1) rx = sz;
if(rx <= l || lx >= r) return 1e18;
if(rx <= r && lx >= l) return mn[x];
int m = (lx+rx)/2;
return min(getmn(l,r,x*2+1,lx,m),getmn(l,r,x*2+2,m,rx))+ op[x];
}
i64 getmx(int l,int r,int x=0,int lx=0,int rx=-1){
if(rx == -1) rx = sz;
if(rx <= l || lx >= r) return -1e18;
if(rx <= r && lx >= l) return mx[x];
int m = (lx+rx)/2;
return max(getmx(l,r,x*2+1,lx,m),getmx(l,r,x*2+2,m,rx)) + op[x];
}
};
VII distribute_candies(VII c,VII l ,VII r,VII v) {
int n = c.size();
int q = l.size();
vector<pair<int,int>>C;
for(int i = 0; i < n; i++) C.push_back({c[i],i});
sort(C.rbegin(), C.rend());
seg st(q);
for(int i = 0; i < q; i++){
st.update(i,q,v[i]);
}
vector<int>ans(n);
function<int(int x)>f=[&](int x){
int l = 0,r=q-1;
int ret = q;
while(l <= r){
int m = (l+r)/2;
i64 MX = st.getmx(0,m+1);
if(MX > x){
r = m-1;
ret = m;
}else{
l = m+1;
}
}
return ret;
};
function<int(int x)>f2=[&](int x){
int l = 0,r=q-1;
int ret = q;
while(l <= r){
int m = (l+r)/2;
i64 MN = st.getmn(0,m+1);
if(MN < x){
r = m-1;
ret = m;
}else{
l = m+1;
}
}
return ret;
};
for(int i = 0; i < q; i++){
int num = C[i].first;
while(true){
bool flag = 1;
while(true){
int idx = f(num);
if(idx == q) break;
i64 rm = st.getmx(0,idx+1)-num;
st.update(idx,q,-rm);
flag = 0;
}
while(true){
int idx = f2(0);
if(idx == q) break;
i64 rm = st.getmn(0,idx+1);
st.update(idx,q,-rm);
flag = 0;
}
if(flag) break;
}
ans[C[i].second] = st.getmn(q-1,q);
}
return ans;
}
// int main(){
// int n,q; cin >> n >> q;
// vector<int>l(q),r(q),v(q),c(n);
// for(int i = 0; i < n; i++) cin >> c[i];
// for(int i = 0; i < q; i++){
// cin >> l[i] >> r[i] >> v[i];
// }
// vector<int>ans = distribute_candies(c,l,r,v);
// for(int x : ans){
// cout << x << ' ';
// }
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1436 ms |
21380 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 |
Correct |
1 ms |
496 KB |
Output is correct |
| 2 |
Correct |
1 ms |
600 KB |
Output is correct |
| 3 |
Execution timed out |
5049 ms |
19796 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
