#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
tuple<long long,long long,long long> queries[400005];
struct node {
long long s,e,m,lazy; pair<long long,long long> least,most; node *l, *r;
node (long long S, long long E) {
s = S, e = E, m = (s+e)/2, least = make_pair(0,s), most = make_pair(0,s), lazy = 0;
if (s != e) l = new node(s,m), r = new node(m+1,e);
}
void propo() {
if (lazy == 0) return;
least.first += lazy, most.first += lazy;
if (s != e) l->lazy += lazy, r->lazy += lazy;
lazy = 0;
}
void update (long long x, long long y, long long nv) {
propo();
if (s == x && e == y) lazy += nv;
else {
if (y <= m) l -> update(x,y,nv);
else if (x > m) r -> update(x,y,nv);
else l -> update(x,m,nv), r -> update(m+1,y,nv);
l -> propo(), r -> propo();
least = min(l->least,r->least), most = max(l->most,r->most);
}
}
pair< pair<long long,long long>, pair<long long,long long> > query (long long x, long long y) {
propo();
if (s == x && e == y) return make_pair(least,most);
else if (y <= m) return l -> query(x,y);
else if (x > m) return r -> query(x,y);
else {
pair< pair<long long,long long>, pair<long long,long long> > q1 = l->query(x,m), q2 = r->query(m+1,y);
return make_pair(min(q1.first,q2.first),max(q1.second,q2.second));
}
}
} *root;
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
long long N = c.size(), Q = l.size();
for (long long i = 0; i < Q; ++i) queries[i*2] = make_tuple(l[i],i+1,v[i]), queries[i*2+1] = make_tuple(r[i]+1,i+1,-v[i]);
sort(queries,queries+Q*2);
root = new node(0,Q);
vector<int> ans;
for (long long i = 0, j = 0; i < N; ++i) {
while (j < Q*2 && get<0>(queries[j]) == i) {
root -> update(get<1>(queries[j]),Q,get<2>(queries[j]));
j++;
}
long long low = -1, high = Q;
while (high-low > 1) {
long long mid = (low+high)/2;
pair< pair<long long,long long>, pair<long long,long long> > q = root -> query(mid,Q);
if (q.second.first-q.first.first >= c[i]) low = mid;
else high = mid;
}
pair< pair<long long,long long>, pair<long long,long long> > q1 = root -> query(low,Q), q2 = root -> query(Q,Q);
if (q1.second.first-q1.first.first < c[i]) ans.push_back(q2.first.first);
else if (q1.first.second > q1.second.second) {
if (q1.first.first < q1.second.first) ans.push_back(q2.first.first-q1.first.first);
else ans.push_back(c[i]-q1.first.first+q2.first.first);
}
else {
if (q1.first.first < q1.second.first) ans.push_back(c[i]-q1.second.first+q2.first.first);
else ans.push_back(q2.first.first-q1.second.first);
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
432 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
188 ms |
112308 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
432 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
