#include "candies.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long
#define add push_back
#define pii pair<int, int>
#define len(a) ((int)(a).size())
#define all(a) a.begin(), a.end()
#define fr first
#define sc second
const int N = 3e5 + 5;
ll C;
struct node {
ll l, r;
ll lv, mv, rv;
void setvalue(ll val){
l = max(0ll, 0ll - val);
r = min(C, C - val);
lv = 0ll;
rv = C;
mv = val;
}
};
ll value(ll num, node& n){
if(n.l <= num && num <= n.r){
return num + n.mv;
}
if(n.r < 0) return n.rv;
if(n.l > C) return n.lv;
if(num < n.l) return n.lv;
return n.rv;
}
void merge(node& c, node& a, node& b){
c.mv = a.mv + b.mv;
c.lv = b.lv;
c.rv = b.rv;
if(a.lv >= b.l) {
c.l = a.l;
c.lv = value(a.lv, b);
}
else if(a.rv < b.l) c.l = C + 1;
else c.l = max(a.l, b.l - a.mv);
c.l = max(c.l, 0 - c.mv);
if(a.rv <= b.r){
c.r = a.r;
c.rv = value(a.rv, b);
}
else if(a.lv > b.r) c.r = 0;
else c.r = min(a.r, b.r - a.mv);
c.r = min(c.r, C - c.mv);
}
node t[4 * N];
void build(int v, int tl, int tr){
if(tl == tr){
t[v].l = 0; t[v].r = C;
t[v].lv = 0; t[v].rv = C;
t[v].mv = 0;
return;
}
int tm = (tl + tr) / 2;
build(2 * v, tl, tm);
build(2 * v + 1, tm + 1, tr);
merge(t[v], t[2 * v], t[2 * v + 1]);
}
void update(int v, int tl, int tr, int ind, ll val){
if(tl == tr){
t[v].setvalue(val);
return;
}
int tm = (tl + tr) / 2;
if(ind <= tm) update(2 * v, tl, tm, ind, val);
else update(2 * v + 1, tm + 1, tr, ind, val);
merge(t[v], t[2 * v], t[2 * v + 1]);
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
C = c[0];
vector<pii> x;
vector<int> ret;
for(int i = 0; i < len(v); i++){
x.add({l[i], -(i + 1)});
x.add({r[i], +(i + 1)});
}
sort(all(x));
build(1, 1, len(v));
int ind = 0;
for(int i = 0; i < len(c); i++){
while(ind < len(x) && x[ind].fr == i && x[ind].sc < 0){
update(1, 1, len(v), -x[ind].sc, v[-x[ind].sc - 1]);
ind++;
}
ret.add(value(0, t[1]));
// cout << t[1].l << " " << t[1].r << " | " << t[1].lv << " " << t[1].mv << " " << t[1].rv << endl;
while(ind < len(x) && x[ind].fr == i && x[ind].sc > 0){
update(1, 1, len(v), x[ind].sc, 0);
ind++;
}
}
return ret;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
329 ms |
32052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
294 ms |
28772 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
