#include "candies.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
//#ifndef DLOCAL
// #define cin fin
// #define cout fout
// ifstream cin(".in");
// ofstream cout(".out");
//#endif
using ll = long long;
using ld = long double;
#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
template<typename T>
struct AINT {
vector<T> aint; int n;
void init(int n_) {
n = n_;
aint.assign(n * 4 + 100, T());
}
template<class CB> void walk(CB&& cb) { walk(cb, -2, n - 1); }
template<class CB> void walk(CB&& cb, int l, int r) { walk(cb, l, r, 1, -2, n - 1); }
template<class CB> void walk(CB&& cb, int l, int r, int node, int cl, int cr) {
if(cr < l || r < cl) return;
if(l <= cl && cr <= r && !cb(aint[node], cl, cr)) return;
int mid = (cl + cr) >> 1, L = 2 * node + 1, R = node * 2;
aint[node].push(aint[L], aint[R]);
walk(cb, l, r, R, mid + 1, cr);
walk(cb, l, r, L, cl, mid);
aint[node].pull(aint[L], aint[R]);
}
};
const ll inf = 1e15 + 5;
int get_mn(int a, int b) {
return min(a, b);
}
struct FirstUnit {
int mx, rightmn, rightP;
int fullmn, fullP;
int lazy;
int sum;
FirstUnit(int b = 0, int c = 0, int d = 0, int f = 0, int h = 0, int e = 0): mx(b), rightmn(c), rightP(d), fullmn(f), fullP(h), lazy(0), sum(e) {;}
void pull(const FirstUnit& a, const FirstUnit& b) {
*this = FirstUnit(max(a.mx, b.mx), -1, -1, min(a.fullmn, b.fullmn), -1, a.sum + b.sum);
if(a.mx >= b.mx) {
if(a.rightmn < b.fullmn) rightmn = a.rightmn, rightP = a.rightP;
else rightmn = b.fullmn, rightP = b.fullP;
}
else
rightmn = b.rightmn, rightP = b.rightP;
fullP = a.fullP;
if(fullmn == b.fullmn) fullP = b.fullP;
return;
}
void apply(int a) {
mx += a; rightmn += a; lazy += a; fullmn += a;
}
void push(FirstUnit& a, FirstUnit& b) { a.apply(lazy); b.apply(lazy); lazy = 0; }
};
std::vector<signed> distribute_candies(std::vector<signed> c, std::vector<signed> l,
std::vector<signed> r, std::vector<signed> v) {
int n = sz(c), q = sz(l);
vector<vector<pii>> opers(n + 1);
for(int i = 0; i < q; i++) opers[l[i]].emplace_back(i, v[i]), opers[r[i] + 1].emplace_back(i, -v[i]);
AINT<FirstUnit> operational;
operational.init(q);
operational.walk([&](auto& a, int cl, int cr) { if(cl != cr) return 1; a.rightP = a.fullP = cl; return 0; });
vector<signed> rez;
operational.walk([&](FirstUnit& a, int cl, int cr) {
a.apply(inf); return 0;
}, -2, q - 1);
operational.walk([&](FirstUnit& a, int cl, int cr) {
a.sum += inf; return 0;
}, -2, -2);
operational.walk([&](FirstUnit& a, int cl, int cr) {
a.apply(-inf); return 0;
}, -1, q - 1);
operational.walk([&](FirstUnit& a, int cl, int cr) {
a.sum += -inf; return 0;
}, -1, -1);
for(int i = 0; i < n; i++) {
for(auto [p, v] : opers[i]) {
operational.walk([&](FirstUnit& a, int cl, int cr) {
a.apply(v); return 0;
}, p, q - 1);
operational.walk([&](FirstUnit& a, int cl, int cr) {
a.sum += v; return 0;
}, p, p);
//cerr << p << ' ' << p << '\t' << v << '\n';
}
int target_bar = c[i];
int lastinterest = -1, lastmin = 0;
operational.walk([&](FirstUnit& a, int cl, int cr) {
if(cr <= lastinterest) return 0;
int R = a.mx - lastmin, L = a.mx - a.rightmn;
//cerr << "\t\t" << cl << ' ' << cr << '\t' << a.mx << ' ' << a.rightmn << ' ' << a.rightP << '\t' << L << ' ' << R << '\n';
if(L > target_bar || L >= R) {
//cerr << "\t\t\t\t\tdobre\n";
lastinterest = a.rightP;
lastmin = a.rightmn;
//cerr << a.rightP << ' ' << a.rightmn << '\n';
return (cl != cr? 1 : 0);
}
else {
return 0;
}
});
int sum = 0, mx = -inf;
operational.walk([&](FirstUnit& a, int cl, int cr) {
//cerr << '\t' << cl << ' ' << cr << '\n';
mx = max(mx, a.mx);
sum += a.sum;
return 0;
}, lastinterest + 1, q - 1);
rez.emplace_back(sum - max(0ll, mx - target_bar - lastmin));
int A = 0, last = -1, cock = 0;
for(int i = 0; i < q; i++) {
int B;
operational.walk([&](FirstUnit& a, int cl, int cr) {
B = a.sum; return 0;
}, i, i);
A = max(0ll, min(A + B, target_bar));
if(A == 0) last = i;
cock += B;
operational.walk([&](FirstUnit& a, int cl, int cr) {
B = a.mx; return 0;
}, i, i);
//if(i + 1 == 1691 || i == 1999) cerr << '\t' << '\t' << B << ' ' << A << '\n';
//cerr << '\t' << cock << ' ' << B << '\n';
if(cock != B) exit(-1);
}
//cerr << A << ' ';
//cerr << last + 1 << ' ' << q - 1 << '\n';
//cerr << lastinterest << ' ' << lastmin << ' ' << sum << ' '<< mx << ' ' << target_bar << '\n';
}
return rez;
}
//26416 -24803 -7010 68416 90723 60899 85738 25434
//26416 -51219 17793 75426 22307 -29824 24839 -60304
#undef int
Compilation message
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:142:18: warning: variable 'last' set but not used [-Wunused-but-set-variable]
142 | int A = 0, last = -1, cock = 0;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
12 ms |
860 KB |
Output is correct |
| 4 |
Correct |
60 ms |
860 KB |
Output is correct |
| 5 |
Correct |
1179 ms |
1124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5063 ms |
70484 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Execution timed out |
5094 ms |
60772 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
480 KB |
Output is correct |
| 3 |
Execution timed out |
5087 ms |
58044 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
12 ms |
860 KB |
Output is correct |
| 4 |
Correct |
60 ms |
860 KB |
Output is correct |
| 5 |
Correct |
1179 ms |
1124 KB |
Output is correct |
| 6 |
Execution timed out |
5063 ms |
70484 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
