#include "candies.h"
#include <vector>
using namespace std;
/*
Consider 'machines' of √Q updates.
Each machine has three numbers a, b and c such that
-> If <= a candies are inserted, a+c candies are obtained.
-> If >= b candies are inserted, b+c candies are obtained.
-> If I candies are inserted, where a <= I <= b, I+c candies are obtained.
To compute the numbers of a machine:
- Pass 0 through the machine to get l
- Pass INF through the machine to get r
- r-l = b-a
*/
int lim; //GOOD
struct machine //GOOD
{
int a;
int b;
int c;
int res(int u) //GOOD
{
if(u < a) return a+c;
else if(a <= u && u <= b) return u+c;
else return b+c;
}
};
machine get_machine(int v)
{
int a, b, c;
c = v;
if(v > 0)
{
a = 0;
b = max(0, lim - v);
}
else
{
a = min(-v, lim);
b = lim;
}
return machine{a, b, c};
}
machine combine(machine A, machine B)
{
/*
1. A.out and B.in are disjoint
1.1 A.out is below B.in
1.2 A.out is above B.in
2. A.out and B.in are not disjoint
2.1 A.out is a superset of B.in
2.2 A.out is a subset of B.in
2.3 A.out is below B.in
2.4 A.out is above B.in
*/
int a, b, c;
if(A.res(lim) < B.a) //1.1
{
a = 0;
b = 0;
c = B.res(0);
}
else if(A.res(0) > B.b)
{
a = 0;
b = 0;
c = B.res(lim);
}
else
{
if(A.res(0) <= B.a && B.b <= A.res(lim))
{
a = B.a - A.c;
b = B.b - A.c;
c = A.c + B.c;
}
else if(B.a <= A.res(0) && A.res(lim) <= B.b)
{
a = A.a;
b = A.b;
c = A.c + B.c;
}
else if(A.res(0) <= B.a)
{
a = B.a - A.c;
b = A.b;
c = A.c + B.c;
}
else
{
a = A.a;
b = B.b - A.c;
c = A.c + B.c;
}
}
return machine{a, b, c};
}
machine empty_machine()
{
return machine{0, lim, +0};
}
struct segtree
{
int l;
int r;
machine x = empty_machine();
segtree* left = NULL;
segtree* right = NULL;
segtree()
{
;
}
segtree(int L, int R)
{
l = L;
r = R;
if(l == r) return;
int m = (l+r)/2;
left = new segtree(l, m);
right = new segtree(m+1, r);
}
void update(int I, machine X)
{
if(I < l || r < I) return;
else if(l == r) x = X;
else
{
left->update(I, X);
right->update(I, X);
x = combine(left->x, right->x);
}
}
int pass_input(int H)
{
return x.res(H);
}
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
int N = c.size();
int Q = l.size();
lim = c[0];
segtree S(0, Q);
vector<int> insertions[N], removals[N];
for(int i = 0; i < Q; i++)
{
insertions[ l[i] ].push_back(i);
removals[ r[i] ].push_back(i);
}
vector<int> res(N, 0);
for(int i = 0; i < N; i++)
{
for(int o: insertions[i])
{
S.update(o, get_machine(v[o]));
}
res[i] = S.pass_input(0);
for(int o: removals[i])
{
S.update(o, empty_machine());
}
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
782 ms |
42704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
537 ms |
26712 KB |
Output is correct |
| 3 |
Correct |
86 ms |
13448 KB |
Output is correct |
| 4 |
Correct |
750 ms |
42684 KB |
Output is correct |
| 5 |
Correct |
754 ms |
42696 KB |
Output is correct |
| 6 |
Correct |
734 ms |
42692 KB |
Output is correct |
| 7 |
Correct |
793 ms |
42696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
