#include "bits/extc++.h"
using namespace std;
template <typename T>
void dbgh(const T& t) {
cerr << t << endl;
}
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t << " | ";
dbgh(u...);
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
<< ": "; \
dbgh(__VA_ARGS__)
#else
#define cerr \
if (false) \
cerr
#define dbg(...)
#endif
#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())
struct Node {
array<array<array<long, 2>, 2>, 3> v;
friend Node operator+(const Node& x, const Node& y) {
Node ans = inf();
for (int a = 0; a < 3; a++) {
for (int b = 0; b < 2; b++) {
for (int c = 0; c < 2; c++) {
for (int d = 0; d < 3; d++) {
for (int e = 0; e < 2; e++) {
auto& cur = ans.v[min(a + d, 2)][b][e];
cur = max(cur, x.v[a][b][c] + y.v[d][c][e]);
}
}
}
}
}
return ans;
}
static Node inf() {
Node ans {};
for (auto& a : ans.v) {
for (auto& b : a) {
for (auto& c : b) {
c = -1e18;
}
}
}
return ans;
}
static Node def() {
Node ans = inf();
ans.v[0][0][0] = ans.v[0][1][1] = ans.v[0][0][1] = ans.v[1][1][0] = 0;
return ans;
}
};
struct Lazy {
long ax, bx;
Lazy& operator+=(const Lazy& x) {
ax += x.ax;
bx += x.bx;
return *this;
}
friend Lazy operator+(Lazy a, const Lazy& b) {
return a += b;
}
Node apply(Node n) const {
for (int i = 0; i < 3; i++) {
for (auto& a : n.v[i]) {
for (auto& b : a) {
b += bx * i;
}
}
n.v[i][0][1] -= ax;
n.v[i][1][0] += ax;
}
return n;
}
static Lazy identity() {
return {0, 0};
}
};
struct TNode {
Node v;
Lazy x;
int lc, rc;
void maintain();
static TNode def() {
return {Node::def(), Lazy::identity(), 0, 0};
}
} heap[512 << 20 / sizeof(TNode)];
int hind = 1;
void TNode::maintain() {
v = x.apply(heap[lc].v + heap[rc].v);
}
int midpoint(int l, int r) {
long x = long(l) + r;
if (x < 0) {
return int((x - 1) / 2);
}
return int(x / 2);
}
void update(int& o, int l, int r, int ql, int qr, const Lazy& x) {
if (!o) {
heap[hind] = TNode::def();
o = hind++;
}
auto& n = heap[o];
if (ql <= l && r <= qr) {
n.x += x;
} else {
int mid = midpoint(l, r);
if (ql <= mid) {
update(n.lc, l, mid, ql, qr, x);
}
if (mid < qr) {
update(n.rc, mid + 1, r, ql, qr, x);
}
}
n.maintain();
}
const int maxa = 2e9 + 5;
int root;
void update(int l, int r, const Lazy& x) {
update(root, -maxa, maxa, l, r, x);
}
void solve() {
heap[0] = TNode::def();
int q, k;
cin >> q >> k;
long ants = 0;
while (q--) {
int t, ind, x;
cin >> t >> ind >> x;
if (t == 1) {
ants += x;
update(ind, maxa, {x, 0});
} else {
update(ind + k, maxa, {-x, 0});
update(ind - k, ind + k - 1, {0, -x});
}
auto& n = heap[root].v;
long ans = 0;
for (auto& a : n.v) {
ans = max(ans, a[0][0]);
}
dbg(ants, ans);
cout << ants - ans << endl;
}
}
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cin.exceptions(ios::failbit);
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
