#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
#ifndef WAIMAI
#include "candies.h"
#endif
#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
#define int long long
#define lpos pos*2
#define rpos pos*2+1
const ll INF = 1e18;
const int SIZE = 2e5 + 5;
int n, q;
vector<pair<int, int>> op[SIZE];
struct Node {
ll sum, mx, mn;
Node() = default;
Node operator + (const Node& r) const {
Node re;
re.sum = sum + r.sum;
re.mn = min(mn, sum + r.mn);
re.mx = max(mx, sum + r.mx);
return re;
}
} node[SIZE * 4];
void upd(int pos, int l, int r, int p, int x) {
if (l == r) {
node[pos].sum += x;
node[pos].mn = node[pos].mx = node[pos].sum;
return;
}
int mid = (l + r) / 2;
if (p <= mid) upd(lpos, l, mid, p, x);
else upd(rpos, mid + 1, r, p, x);
node[pos] = node[lpos] + node[rpos];
}
ll que(int pos, int l, int r, int L, int R) {
if (l == L && r == R) return node[pos].sum;
int mid = (L + R) / 2;
if (r <= mid) return que(lpos, l, r, L, mid);
if (l > mid) return que(rpos, l, r, mid + 1, R);
return que(lpos, l, mid, L, mid) + que(rpos, mid + 1, r, mid + 1, R);
}
ll que(int l, int r) {
if (l > r) return 0;
return que(1, l, r, 0, q);
}
tuple<int, ll, ll> sch(int pos, int l, int r, int lim, ll psum = 0, ll pmx = -INF, ll pmn = INF) {
if (l == r) return {l, max(pmx, psum + node[pos].mx), min(pmn, psum + node[pos].mn)};
int mid = (l + r) / 2;
ll lsum = psum + node[lpos].sum;
ll rmx = max(pmx, lsum + node[rpos].mx);
ll rmn = min(pmn, lsum + node[rpos].mn);
if (rmx - rmn >= lim) return sch(rpos, mid + 1, r, lim, lsum, pmx, pmn);
else return sch(lpos, l, mid, lim, psum, rmx, rmn);
}
int sch2(int pos, int l, int r, int ty, ll x, ll psum = 0, ll pmx = -INF, ll pmn = INF) {
if (l == r) return l;
int mid = (l + r) / 2;
ll lsum = psum + node[lpos].sum;
ll rmx = max(pmx, lsum + node[rpos].mx);
ll rmn = min(pmn, lsum + node[rpos].mn);
// debug(l, r, ty, x, lsum, rmx, rmn);
if ((ty == 1 && rmn == x) || (ty == 0 && rmx == x)) return sch2(rpos, mid + 1, r, ty, x, lsum, pmx, pmn);
else return sch2(lpos, l, mid, ty, x, psum, rmx, rmn);
}
int sch3(int pos, int l, int r) {
if (l == r) return l;
int mid = (l + r) / 2;
ll rmn = node[lpos].sum + node[rpos].mn;
if (rmn == node[pos].mn) return sch3(rpos, mid + 1, r);
return sch3(lpos, l, mid);
}
vector<int32_t> distribute_candies(vector<int32_t> c, vector<int32_t> l, vector<int32_t> r, vector<int32_t> v) {
n = c.size();
q = l.size();
FOR (i, 0, q - 1) {
op[l[i]].pb(i + 1, v[i]);
op[r[i] + 1].pb(i + 1, -v[i]);
}
vector<int32_t> ans(n);
FOR (i, 0, n - 1) {
// debug(i);
for (auto [p, x] : op[i]) upd(1, 0, q, p, x);
if (node[1].mx - node[1].mn < c[i]) {
int p = sch3(1, 0, q);
ans[i] = que(p + 1, q);
// debug(p);
continue;
}
auto [lp, mx, mn] = sch(1, 0, q, c[i]);
int ty = (que(0, lp) == mx);
int rp = sch2(1, 0, q, ty, (ty ? mn : mx));
// debug(lp, rp, ty, mx, mn);
ans[i] = (ty ? que(rp + 1, q) : c[i] + que(rp + 1, q));
}
return ans;
}
/*
in1
3
10 15 13
2
0 2 20
0 1 -11
out1
0 4 13
*/
#ifdef WAIMAI
int main() {
int n;
assert(1 == scanf("%d", &n));
vector<int> c(n);
for(int i = 0; i < n; ++i) {
assert(scanf("%d", &c[i]) == 1);
}
int q;
assert(1 == scanf("%d", &q));
vector<int> l(q), r(q), v(q);
for(int i = 0; i < q; ++i) {
assert(scanf("%d %d %d", &l[i], &r[i], &v[i]) == 3);
}
vector<int> ans = distribute_candies(c, l, r, v);
for(int i = 0; i < n; ++i) {
if (i > 0) {
printf(" ");
}
printf("%d", ans[i]);
}
printf("\n");
fclose(stdout);
return 0;
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5008 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
5272 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
314 ms |
39672 KB |
Output is correct |
| 2 |
Correct |
329 ms |
38800 KB |
Output is correct |
| 3 |
Correct |
300 ms |
38728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
192 ms |
33912 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5008 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
5272 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
