#include "candies.h"
#include <vector>
#include <iostream>
using namespace std;
const long long INF = 1'000'000'000'000'000'000;
struct segtree //min, max, range add
{
long long l;
long long r;
long long mn = 0;
long long mx = 0;
long long lp = 0;
segtree* left = NULL;
segtree* right = NULL;
segtree()
{
;
}
segtree(long long L, long long R)
{
l = L;
r = R;
if(l == r) return;
long long m = (l+r+10)/2 - 5;
left = new segtree(l, m);
right = new segtree(m+1, r);
}
long long rangemin(long long L, long long R)
{
if(R < l || r < L) return INF;
else if(L <= l && r <= R) return mn;
else return lp + min(left->rangemin(L, R), right->rangemin(L, R));
}
long long rangemax(long long L, long long R)
{
if(R < l || r < L) return -INF;
else if(L <= l && r <= R) return mx;
else return lp + max(left->rangemax(L, R), right->rangemax(L, R));
}
void add(long long L, long long R, long long V)
{
if(R < l || r < L) return;
// cerr << "adding to " << l << ' ' << r << ": " << L << ' ' << R << ' ' << V << '\n';
if(L <= l && r <= R)
{
mn += V;
mx += V;
lp += V;
}
else
{
left->add(L, R, V);
right->add(L, R, V);
mn = lp + min(left->mn, right->mn);
mx = lp + max(left->mx, right->mx);
}
}
};
vector<int> distribute_candies(vector<int> c1, vector<int> l1, vector<int> r1, vector<int> v1)
{
long long N = c1.size();
long long Q = l1.size();
vector<long long> c(N);
vector<long long> l(Q), r(Q), v(Q);
for(int i = 0; i < N; i++) c[i] = c1[i];
for(int j = 0; j < Q; j++)
{
l[j] = l1[j];
r[j] = r1[j];
v[j] = v1[j];
}
segtree S(-3, Q-1);
S.add(-3, -3, -INF);
S.add(-2, -2, +INF);
vector<long long> insertions[N], removals[N];
for(long long i = 0; i < Q; i++)
{
insertions[ l[i] ].push_back(i);
removals[ r[i] ].push_back(i);
}
vector<long long> res(N, 0);
long long curr_upd_sum = 0;
// for(long long j = -1; j <= Q-1; j++) cerr << S.rangemax(j, j) << ' ';
// cerr << '\n';
for(long long i = 0; i < N; i++)
{
// cerr << "i = " << i << '\n';
for(long long o: insertions[i])
{
// cerr << "inserting " << o << ": " << l[o] << ' ' << r[o] << ' ' << v[o] << '\n';
S.add(o, Q-1, +v[o]);
curr_upd_sum += v[o];
// cerr << "segment tree: ";
// for(long long j = -1; j <= Q-1; j++) cerr << S.rangemax(j, j) << ' ';
// cerr << '\n';
}
long long lower_bound = 0;
// cerr << S.rangemax(-1, Q-1) << ' ' << S.rangemin(-1, Q-1) << '\n';
long long last_good = Q-1;
// for(last_good = Q-1; last_good >= 0; last_good--)
// {
// if(S.rangemax(last_good-1, Q-1) - S.rangemin(last_good-1, Q-1) > (long long)c[i])
// break;
// }
// cerr << "last_good = " << last_good << '\n';
for(long long bit = 19; bit >= 0; bit--)
{
long long new_good = last_good - (1 << bit);
if(new_good < -1) continue;
if(S.rangemax(new_good, Q-1) - S.rangemin(new_good, Q-1) <= (long long)c[i])
last_good = new_good;
}
// cerr << "last_good = " << last_good << '\n';
if(0 <= S.rangemin(0, Q-1) && S.rangemax(0, Q-1) <= c[i])
lower_bound = 0;
else if(S.rangemax(last_good-1, last_good-1) < S.rangemax(last_good, last_good))
lower_bound = S.rangemax(last_good, Q-1) - (long long)c[i];
else
lower_bound = S.rangemin(last_good, Q-1);
// cerr << "curr_upd_sum = " << curr_upd_sum << ", lower_bound = " << lower_bound << '\n';
res[i] = (curr_upd_sum - lower_bound);
for(long long o: removals[i])
{
// cerr << "removing " << o << '\n';
S.add(o, Q-1, -v[o]);
curr_upd_sum -= v[o];
}
// cerr << "\n\n";
}
vector<int> res1(N);
for(int i = 0; i < N; i++) res1[i] = res[i];
return res1;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
2 ms |
716 KB |
Output is correct |
4 |
Correct |
2 ms |
716 KB |
Output is correct |
5 |
Correct |
6 ms |
844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1571 ms |
62384 KB |
Output is correct |
2 |
Correct |
1653 ms |
61644 KB |
Output is correct |
3 |
Correct |
1699 ms |
61448 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
409 ms |
43436 KB |
Output is correct |
3 |
Correct |
355 ms |
17800 KB |
Output is correct |
4 |
Correct |
1359 ms |
63452 KB |
Output is correct |
5 |
Correct |
1558 ms |
63848 KB |
Output is correct |
6 |
Correct |
1389 ms |
64336 KB |
Output is correct |
7 |
Correct |
1376 ms |
63580 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
162 ms |
40760 KB |
Output is correct |
4 |
Correct |
324 ms |
16744 KB |
Output is correct |
5 |
Correct |
1018 ms |
56220 KB |
Output is correct |
6 |
Correct |
1022 ms |
56856 KB |
Output is correct |
7 |
Correct |
981 ms |
57468 KB |
Output is correct |
8 |
Correct |
923 ms |
56112 KB |
Output is correct |
9 |
Correct |
833 ms |
57588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
2 ms |
716 KB |
Output is correct |
4 |
Correct |
2 ms |
716 KB |
Output is correct |
5 |
Correct |
6 ms |
844 KB |
Output is correct |
6 |
Correct |
1571 ms |
62384 KB |
Output is correct |
7 |
Correct |
1653 ms |
61644 KB |
Output is correct |
8 |
Correct |
1699 ms |
61448 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
409 ms |
43436 KB |
Output is correct |
11 |
Correct |
355 ms |
17800 KB |
Output is correct |
12 |
Correct |
1359 ms |
63452 KB |
Output is correct |
13 |
Correct |
1558 ms |
63848 KB |
Output is correct |
14 |
Correct |
1389 ms |
64336 KB |
Output is correct |
15 |
Correct |
1376 ms |
63580 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
162 ms |
40760 KB |
Output is correct |
19 |
Correct |
324 ms |
16744 KB |
Output is correct |
20 |
Correct |
1018 ms |
56220 KB |
Output is correct |
21 |
Correct |
1022 ms |
56856 KB |
Output is correct |
22 |
Correct |
981 ms |
57468 KB |
Output is correct |
23 |
Correct |
923 ms |
56112 KB |
Output is correct |
24 |
Correct |
833 ms |
57588 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
312 ms |
16936 KB |
Output is correct |
27 |
Correct |
385 ms |
43048 KB |
Output is correct |
28 |
Correct |
1261 ms |
62088 KB |
Output is correct |
29 |
Correct |
1374 ms |
62488 KB |
Output is correct |
30 |
Correct |
1423 ms |
62756 KB |
Output is correct |
31 |
Correct |
1411 ms |
62868 KB |
Output is correct |
32 |
Correct |
1370 ms |
63168 KB |
Output is correct |