#include "candies.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll INF = 1e18;
struct Seg{
pair<ll, ll> tree[800800];
ll lazy[800800];
pair<ll, ll> combine(pair<ll, ll> x, pair<ll, ll> y){
return pair<ll, ll>(max(x.first, y.first), min(x.second, y.second));
}
void propagate(int i, int l, int r){
tree[i].first += lazy[i];
tree[i].second += lazy[i];
if (l!=r) lazy[i<<1] += lazy[i], lazy[i<<1|1] += lazy[i];
lazy[i] = 0;
}
void update(int i, int l, int r, int s, int e, ll x){
propagate(i, l, r);
if (r<s || e<l) return;
if (s<=l && r<=e){
lazy[i] += x;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i<<1, l, m, s, e, x);
update(i<<1|1, m+1, r, s, e, x);
tree[i] = combine(tree[i<<1], tree[i<<1|1]);
}
pair<ll, ll> query(int i, int l, int r, int s, int e){
propagate(i, l, r);
if (r<s || e<l) return {-INF, INF};
if (s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
return combine(query(i<<1, l, m, s, e), query(i<<1|1, m+1, r, s, e));
}
int left_bound(int i, int l, int r, int x, pair<ll, ll> cur){
propagate(i, l, r);
assert(cur.first-cur.second<=x);
auto p = combine(cur, tree[i]);
if (p.first-p.second<=x) return -1;
if (l==r) return l;
int m = (l+r)>>1;
int tmp = left_bound(i<<1|1, m+1, r, x, cur);
if (tmp!=-1) return tmp;
return left_bound(i<<1, l, m, x, combine(cur, tree[i<<1|1]));
}
}tree;
vector<int> qb[200200], qe[200200];
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
int n = c.size();
int q = v.size();
vector<int> ret(n);
for (int i=0;i<q;i++){
qb[l[i]+1].push_back(i+1);
qe[r[i]+1].push_back(i+1);
}
for (int i=1;i<=n;i++){
for (auto &x:qe[i-1]) tree.update(1, 0, q, x, q, -v[x-1]);
for (auto &x:qb[i]) tree.update(1, 0, q, x, q, v[x-1]);
int idx = tree.left_bound(1, 0, q, c[i-1], {-INF, INF});
//printf("%d: %d %lld %lld\n", i, idx, tree.tree[1].first, tree.tree[1].second);
if (idx==-1) ret[i-1] = tree.query(1, 0, q, q, q).first - tree.query(1, 0, q, 0, q).second;
else{
int tmp = tree.query(1, 0, q, idx, idx).first;
auto p = tree.query(1, 0, q, idx, q);
if (tmp==p.first) ret[i-1] = tree.query(1, 0, q, q, q).first - p.second;
else if (tmp==p.second) ret[i-1] = c[i-1] - p.first + tree.query(1, 0, q, q, q).first;
else exit(1);
}
}
return ret;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
22220 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
189 ms |
40564 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
22248 KB |
Output is correct |
| 2 |
Runtime error |
67 ms |
33820 KB |
Execution failed because the return code was nonzero |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
22220 KB |
Output is correct |
| 2 |
Correct |
10 ms |
22244 KB |
Output is correct |
| 3 |
Correct |
110 ms |
32732 KB |
Output is correct |
| 4 |
Correct |
119 ms |
24796 KB |
Output is correct |
| 5 |
Correct |
267 ms |
35248 KB |
Output is correct |
| 6 |
Correct |
292 ms |
35292 KB |
Output is correct |
| 7 |
Runtime error |
133 ms |
35164 KB |
Execution failed because the return code was nonzero |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
22220 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
