#include "candies.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
typedef long long ll;
#define ar array
const ll inf = 1e18;
const int N = 2e5 + 5;
struct ST{
ll tree[N << 2];
void set(int i, ll v, int lx = 0, int rx = N, int x = 1){
if(lx == rx) { tree[x] = v; return; }
int m = (lx + rx) >> 1;
if(i <= m) set(i, v, lx, m, x << 1);
else set(i, v, m + 1, rx, x << 1 | 1);
tree[x] = min(tree[x << 1], tree[x << 1 | 1]);
}
int get(int v, int lx = 0, int rx = N, int x = 1){
if(lx == rx) return lx;
int m = (lx + rx) >> 1;
if(tree[x << 1] <= v) return get(v, lx, m, x << 1);
else return get(v, m + 1, rx, x << 1 | 1);
}
ll mn(int l, int r, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l) return inf;
if(lx >= l && rx <= r) return tree[x];
int m = (lx + rx) >> 1;
return min(mn(l, r, lx, m, x << 1), mn(l, r, m + 1, rx, x << 1 | 1));
}
}tree, T;
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n = c.size();
int q = l.size();
vector<int> p(n);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int i, int j){
return c[i] < c[j];
});
set<int> ss;
set<ar<int, 2>> tt;
ss.insert(-1);
vector<ll> a(q);
for(int i=0;i<q;i++){
tree.set(i, inf), T.set(i, inf);
a[i] = min(a[i], (ll)c[p[0]]);
a[i] = max(a[i], 0ll);
a[i] += v[i];
if(a[i] > c[p[0]]){
tree.set(i, a[i]);
ss.insert(i);
} else if(a[i] < 0){
if(!ss.empty() && a[(*--ss.end())] >= 0){
T.set(i, 0 - a[i]);
}
ss.insert(i);
}
if(i + 1 < q) a[i + 1] = a[i];
}
vector<ll> suff(q + 1);
for(int i=q-1;~i;i--){
suff[i] = suff[i + 1] + v[i];
}
vector<int> res(n);
for(int i=0;i<n;i++){
int j = tree.get(c[p[i]]);
while(j < q){
tree.set(j, inf);
ss.erase(j);
auto it = ss.upper_bound(j);
vector<int> er;
assert(a[j] <= c[p[i]]);
int d = (c[p[i]] - a[j]);
while(it != ss.end()){
if(a[*it] > c[p[i - 1]]){
a[*it] += d;
tree.set(*it, a[*it]);
break;
} else {
a[*it] += d;
T.set(*it, inf);
if(a[*it] < 0){
T.set(*it, 0 - a[*it]);
break;
}
er.push_back(*it);
it++;
}
}
for(auto x : er){
ss.erase(x);
}
j = tree.get(c[p[i]]);
}
j = T.get(c[p[i]] - c[p[0]]);
while(j < q){
ss.erase(j);
T.set(j, inf);
auto it = ss.upper_bound(j);
if(it != ss.end() && a[*it] < 0){
T.set(*it, 0 - a[*it]);
}
j = T.get(c[p[i]] - c[p[0]]);
}
assert(!ss.empty());
int last = (*--ss.end());
res[p[i]] = suff[last + 1];
if(~last && a[last] >= 0){
res[p[i]] += c[p[i]];
}
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
360 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
481 ms |
28892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
360 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
