#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 200005;
struct Query {
int l, r, v;
} qr[MAXN];
vector<ii> B[MAXN];
int result[MAXN];
int capa[MAXN], nArr, numQuery;
void sub1(void) {
for (int i = 1; i <= nArr; ++i)
result[i] = 0;
for (int t = 1; t <= numQuery; ++t) {
int l(qr[t].l), r(qr[t].r), v(qr[t].v);
for (int i = l; i <= r; ++i)
result[i] = min(capa[i], max(0, result[i] + v));
}
}
struct SegNode {
ll minv, maxv, sumAdd, lz;
} seg[4 * MAXN];
void pushDown(int id) {
ll &lz(seg[id].lz);
id <<= 1;
seg[id] = {seg[id].minv + lz, seg[id].maxv + lz, seg[id].sumAdd + lz, seg[id].lz + lz};
seg[id | 1] = {seg[id | 1].minv + lz, seg[id | 1].maxv + lz, seg[id | 1].sumAdd + lz, seg[id | 1].lz + lz};
lz = 0;
}
ll sumAll(0);
void update(int id, int l, int r, int u, int v, int k) {
seg[id].sumAdd += k;
if(u <= l && r <= v) {
seg[id] = {seg[id].minv + k, seg[id].maxv + k, seg[id].sumAdd, seg[id].lz + k};
return;
}
if(seg[id].lz)
pushDown(id);
int mid = (l + r) >> 1;
if(mid >= u)
update(id << 1, l, mid, u, v, k);
if(mid + 1 <= v)
update(id << 1 | 1, mid + 1, r, u, v, k);
seg[id].minv = min(seg[id << 1].minv, seg[id << 1 | 1].minv);
seg[id].maxv = max(seg[id << 1].maxv, seg[id << 1 | 1].maxv);
}
int query(int capa) {
ll minNow(1e18), maxNow(-1e18);
int id(1), l(1), r(numQuery);
while(l < r) {
int mid = (l + r) >> 1;
if(seg[id].lz)
pushDown(id);
id <<= 1;
if(max(maxNow, seg[id | 1].maxv) - min(minNow, seg[id | 1].minv) > capa) {
l = mid + 1;
id |= 1;
} else {
maxNow = max(maxNow, seg[id | 1].maxv);
minNow = min(minNow, seg[id | 1].minv);
r = mid;
}
}
maxNow = max(maxNow, seg[id].maxv);
minNow = min(minNow, seg[id].minv);
if(seg[id].minv < sumAll) {
return capa - (maxNow - sumAll);
} else {
return sumAll - minNow;
}
}
void magicFunc(void) {
for (int t = 1; t <= numQuery; ++t) {
int l(qr[t].l), r(qr[t].r), v(qr[t].v);
B[l].push_back(ii(t, v));
B[r + 1].push_back(ii(t, -v));
}
for (int i = 1; i <= nArr; ++i) {
for (int it = 0; it < sz(B[i]); ++it) {
int j(B[i][it].fi), v(B[i][it].se);
update(1, 1, numQuery, j, numQuery, v);
sumAll += v;
}
/*cout << result[i] << ' ' << query(capa[i]) << '\n';
if(query(capa[i]) != result[i])
exit(1);*/
result[i] = query(capa[i]);
}
}
vector<int> distribute_candies(vector<int> _C, vector<int> _L, vector<int> _R, vector<int> _V) {
nArr = sz(_C);
for (int i = 1; i <= nArr; ++i)
capa[i] = _C[i - 1];
numQuery = sz(_L);
for (int t = 1; t <= numQuery; ++t)
qr[t] = {_L[t - 1] + 1, _R[t - 1] + 1, _V[t - 1]};
if(max(nArr, numQuery) <= 2000) {
sub1();
} else {
magicFunc();
}
vector<int> ans;
for (int i = 1; i <= nArr; ++i)
ans.push_back(result[i]);
return ans;
}
#ifdef Nhoksocqt1
int main(void) {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define TASK "candies"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
vector<int> C, L, R, V;
int N, Q;
cin >> N >> Q;
C.resize(N);
for (int i = 0; i < N; ++i) {
cin >> C[i];
C[i] = Random(100, 1e5); cout << C[i] << " \n"[i + 1 == N];
}
L.resize(Q), R.resize(Q), V.resize(Q);
for (int t = 0; t < Q; ++t) {
cin >> L[t] >> R[t] >> V[t];
L[t] = Random(0, N - 1), R[t] = Random(L[t], N - 1), V[t] = Random(-1e5, 1e5); cout << L[t] << ' ' << R[t] << ' ' << V[t] << '\n';
}
vector<int> ans = distribute_candies(C, L, R, V);
cout << "ANSWER: ";
for (int it = 0; it < sz(ans); ++it)
cout << ans[it] << ' '; cout << '\n';
return 0;
}
#endif // Nhoksocqt1
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
8536 KB |
Output is correct |
2 |
Correct |
1 ms |
8540 KB |
Output is correct |
3 |
Correct |
2 ms |
8540 KB |
Output is correct |
4 |
Correct |
2 ms |
8540 KB |
Output is correct |
5 |
Correct |
3 ms |
8540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
286 ms |
40312 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
8540 KB |
Output is correct |
2 |
Incorrect |
186 ms |
38088 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
8540 KB |
Output is correct |
2 |
Correct |
2 ms |
8540 KB |
Output is correct |
3 |
Correct |
80 ms |
36360 KB |
Output is correct |
4 |
Correct |
44 ms |
12768 KB |
Output is correct |
5 |
Incorrect |
125 ms |
40564 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
8536 KB |
Output is correct |
2 |
Correct |
1 ms |
8540 KB |
Output is correct |
3 |
Correct |
2 ms |
8540 KB |
Output is correct |
4 |
Correct |
2 ms |
8540 KB |
Output is correct |
5 |
Correct |
3 ms |
8540 KB |
Output is correct |
6 |
Incorrect |
286 ms |
40312 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |