#include "candies.h"
#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;
struct node{
int l, r;
int lv, mv, rv;
};
int C;
node t[4 * N];
int value(int num, node& a){
if(num < a.l) return a.lv;
if(num > a.r) return a.rv;
return num + a.mv;
}
void merge(node& c, node& a, node& b){
c.lv = value(a.lv, b);
c.rv = value(a.rv, b);
c.mv = a.mv + b.mv;
c.l = max(b.lv - a.mv + 1, a.l);
c.r = min(b.rv - a.mv - 1, a.r);
}
void build(int v, int tl, int tr){
if(tl == tr){
t[v].l = 0, t[v].r = 300000;
t[v].lv = t[v].mv = t[v].rv = 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, int val){
if(tl == tr){
t[v].l = max(0, 0 - val); t[v].lv = 0;
t[v].r = min(C, C - val); t[v].rv = C;
t[v].mv = 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(l); 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(x); 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]));
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 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
383 ms |
28416 KB |
Output isn't correct |
| 2 |
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 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
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 |
- |
