#include <bits/stdc++.h>
#define ar array<int, 3>
#define ii pair<long long, long long>
using namespace std;
int N, Q;
ii t[200002 << 2];
long long lazy[200002 << 2];
void push(int v){
if(lazy[v] == 0) return;
t[v * 2].first += lazy[v];
t[v * 2 + 1].first += lazy[v];
t[v * 2].second += lazy[v];
t[v * 2 + 1].second += lazy[v];
lazy[v * 2] += lazy[v];
lazy[v * 2 + 1] += lazy[v];
lazy[v] = 0;
return;
}
void ins(int v, int tl, int tr, int l, int r, int val){
if(l > r) return;
if(tl == l && tr == r){
t[v].first += val * 1ll; t[v].second += val * 1ll;
lazy[v] += val * 1ll;
return;
}
push(v);
int tm = (tl + tr) >> 1;
ins(v * 2, tl, tm, l, min(r, tm), val);
ins(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, val);
t[v].first = max(t[v * 2].first, t[v * 2 + 1].first);
t[v].second = min(t[v * 2].second, t[v * 2 + 1].second);
}
ii query(int v, int tl, int tr, int l, int r){
if(l > r) return {LLONG_MIN, LLONG_MAX};
if(tl == l && tr == r) return t[v];
push(v);
int tm = (tl + tr) >> 1;
ii ll = query(v * 2, tl, tm, l, min(r, tm));
ii rr = query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
ii res = ll; res.first = max(res.first, rr.first); res.second = min(res.second, rr.second);
return res;
}
vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V){
N = C.size(); Q = L.size(); vector<int> ans(200002);
priority_queue<ar, vector<ar>, greater<ar>> pq;
for(int i = 0; i < Q; i++){
pq.push({L[i], V[i], i + 1});
pq.push({R[i] + 1, -V[i], i + 1});
}
for(int i = 0; i < N; i++){
while(!pq.empty() && pq.top()[0] == i){
ins(1, 0, Q, pq.top()[2], Q, pq.top()[1]);
pq.pop();
}
int l = 0, r = Q; bool chk = false;
while(l < r){
int mid = (l + r) >> 1;
ii res = query(1, 0, Q, mid, Q);
long long diff = res.first - res.second;
if(diff > C[i]){
chk = true; l = mid + 1;
}
else r = mid;
}
if(!chk) ans[i] = int((query(1, 0, Q, Q, Q)).first);
else{
long long cur = (query(1, 0, Q, l, Q)).first;
long long bef = (query(1, 0, Q, l - 1, l - 1)).first;
long long last = (query(1, 0, Q, Q, Q)).first;
ii res = query(1, 0, Q, l, Q);
if(bef < cur){
// Hit top
ans[i] = C[i] - (res.first - last);
}
else{
// Hit bottom
ans[i] = last - res.second;
}
}
ans[i] = max(ans[i], 0);
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1022 ms |
24436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
