#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#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())
namespace IO {
char buf[1 << 20];
int bind, bend;
char nc() {
if (bind == bend) {
bend = int(fread(buf, 1, sizeof(buf), stdin));
bind = 0;
}
return buf[bind++];
}
int ni() {
int ans = 0;
char c;
while ((c = nc()) >= '0') {
ans = ans * 10 + c - '0';
}
return ans;
}
} // namespace IO
using IO::ni;
struct Node {
array<array<array<long, 2>, 2>, 2> v;
Node() : v(Node::def().v) {}
Node(bool) : v {} {}
friend Node operator+(const Node& x, const Node& y) {
Node ans = inf();
for (int a = 0; a < 2; a++) {
for (int b = 0; b < 2; b++) {
for (int c = 0; c < 2; c++) {
for (int d = 0; d < 2; d++) {
for (int e = 0; e < 2; e++) {
auto& cur = ans.v[min(a + d, 1)][b][e];
cur = max(cur, x.v[a][b][c] + y.v[d][c][e]);
}
}
}
}
}
return ans;
}
static Node inf() {
Node ans(true);
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 < 2; 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};
}
};
const int maxn = 1 << 21, tmaxn = maxn << 1;
Node v[tmaxn];
Lazy lazy[tmaxn];
void update(int o, int l, int r, int ql, int qr, const Lazy& x) {
int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
if (ql <= l && r <= qr) {
lazy[o] += x;
} else {
if (ql <= mid) {
update(lc, l, mid, ql, qr, x);
}
if (mid < qr) {
update(rc, mid + 1, r, ql, qr, x);
}
}
if (l == r) {
v[o] = lazy[o].apply(Node::def());
} else {
v[o] = lazy[o].apply(v[lc] + v[rc]);
}
}
void update(int l, int r, const Lazy& x) {
dbg(l, r, x.ax, x.bx);
update(1, 0, maxn - 1, l, r, x);
}
void solve() {
int q = ni(), k = ni();
int arr[q][3];
for (auto& [a, b, c] : arr) {
a = ni();
b = ni();
c = ni();
}
vector<int> comp;
for (auto& [t, ind, _x] : arr) {
if (t == 1) {
comp.push_back(ind);
} else {
comp.push_back(ind + k);
comp.push_back(ind - k);
comp.push_back(ind + k - 1);
}
}
sort(begin(comp), end(comp));
comp.erase(unique(begin(comp), end(comp)), comp.end());
auto cg = [&](int x) -> int {
return int(lower_bound(begin(comp), end(comp), x) - comp.begin());
};
long ants = 0;
for (auto& [t, ind, x] : arr) {
if (t == 1) {
ants += x;
update(cg(ind), maxn - 1, {x, 0});
} else {
update(cg(ind + k), maxn - 1, {-x, 0});
update(cg(ind - k), cg(ind + k - 1), {0, -x});
}
auto& n = v[1];
long ans = 0;
for (auto& a : n.v) {
ans = max({ans, a[0][0], a[1][0]});
}
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 |
164 ms |
262976 KB |
Output is correct |
2 |
Correct |
167 ms |
262980 KB |
Output is correct |
3 |
Correct |
163 ms |
263040 KB |
Output is correct |
4 |
Correct |
163 ms |
263060 KB |
Output is correct |
5 |
Correct |
173 ms |
262948 KB |
Output is correct |
6 |
Correct |
182 ms |
263124 KB |
Output is correct |
7 |
Correct |
168 ms |
263240 KB |
Output is correct |
8 |
Correct |
170 ms |
263084 KB |
Output is correct |
9 |
Correct |
184 ms |
263116 KB |
Output is correct |
10 |
Correct |
182 ms |
263332 KB |
Output is correct |
11 |
Correct |
179 ms |
263388 KB |
Output is correct |
12 |
Correct |
186 ms |
263388 KB |
Output is correct |
13 |
Correct |
191 ms |
263404 KB |
Output is correct |
14 |
Correct |
176 ms |
263444 KB |
Output is correct |
15 |
Correct |
178 ms |
263528 KB |
Output is correct |
16 |
Correct |
191 ms |
263424 KB |
Output is correct |
17 |
Correct |
172 ms |
263272 KB |
Output is correct |
18 |
Correct |
177 ms |
263360 KB |
Output is correct |
19 |
Correct |
191 ms |
263436 KB |
Output is correct |
20 |
Correct |
168 ms |
263320 KB |
Output is correct |
21 |
Correct |
177 ms |
263424 KB |
Output is correct |
22 |
Correct |
193 ms |
263276 KB |
Output is correct |
23 |
Correct |
175 ms |
263480 KB |
Output is correct |
24 |
Correct |
172 ms |
263236 KB |
Output is correct |
25 |
Correct |
181 ms |
263348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
171 ms |
262996 KB |
Output is correct |
2 |
Correct |
160 ms |
262964 KB |
Output is correct |
3 |
Correct |
182 ms |
262992 KB |
Output is correct |
4 |
Correct |
1844 ms |
285508 KB |
Output is correct |
5 |
Correct |
1006 ms |
276248 KB |
Output is correct |
6 |
Correct |
2101 ms |
289136 KB |
Output is correct |
7 |
Correct |
1002 ms |
276500 KB |
Output is correct |
8 |
Correct |
2536 ms |
293756 KB |
Output is correct |
9 |
Correct |
1911 ms |
289836 KB |
Output is correct |
10 |
Correct |
2507 ms |
294092 KB |
Output is correct |
11 |
Correct |
1874 ms |
289844 KB |
Output is correct |
12 |
Correct |
951 ms |
274308 KB |
Output is correct |
13 |
Correct |
1259 ms |
278072 KB |
Output is correct |
14 |
Correct |
1930 ms |
286672 KB |
Output is correct |
15 |
Correct |
1944 ms |
286556 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
161 ms |
262988 KB |
Output is correct |
2 |
Correct |
947 ms |
273956 KB |
Output is correct |
3 |
Correct |
1243 ms |
277720 KB |
Output is correct |
4 |
Correct |
1919 ms |
286100 KB |
Output is correct |
5 |
Correct |
1917 ms |
286200 KB |
Output is correct |
6 |
Correct |
2123 ms |
287904 KB |
Output is correct |
7 |
Correct |
307 ms |
266564 KB |
Output is correct |
8 |
Correct |
1109 ms |
278524 KB |
Output is correct |
9 |
Correct |
1585 ms |
283704 KB |
Output is correct |
10 |
Correct |
2719 ms |
309560 KB |
Output is correct |
11 |
Correct |
2793 ms |
319680 KB |
Output is correct |
12 |
Correct |
2800 ms |
319508 KB |
Output is correct |
13 |
Correct |
2800 ms |
319484 KB |
Output is correct |
14 |
Correct |
2789 ms |
319876 KB |
Output is correct |
15 |
Correct |
2620 ms |
319224 KB |
Output is correct |
16 |
Correct |
2736 ms |
319756 KB |
Output is correct |
17 |
Correct |
3017 ms |
319696 KB |
Output is correct |
18 |
Correct |
3356 ms |
319424 KB |
Output is correct |
19 |
Correct |
3314 ms |
319832 KB |
Output is correct |
20 |
Correct |
3260 ms |
319228 KB |
Output is correct |
21 |
Correct |
3341 ms |
319744 KB |
Output is correct |
22 |
Correct |
3420 ms |
319364 KB |
Output is correct |
23 |
Correct |
3351 ms |
318908 KB |
Output is correct |
24 |
Correct |
3252 ms |
316192 KB |
Output is correct |
25 |
Correct |
3403 ms |
316588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
164 ms |
262976 KB |
Output is correct |
2 |
Correct |
167 ms |
262980 KB |
Output is correct |
3 |
Correct |
163 ms |
263040 KB |
Output is correct |
4 |
Correct |
163 ms |
263060 KB |
Output is correct |
5 |
Correct |
173 ms |
262948 KB |
Output is correct |
6 |
Correct |
182 ms |
263124 KB |
Output is correct |
7 |
Correct |
168 ms |
263240 KB |
Output is correct |
8 |
Correct |
170 ms |
263084 KB |
Output is correct |
9 |
Correct |
184 ms |
263116 KB |
Output is correct |
10 |
Correct |
182 ms |
263332 KB |
Output is correct |
11 |
Correct |
179 ms |
263388 KB |
Output is correct |
12 |
Correct |
186 ms |
263388 KB |
Output is correct |
13 |
Correct |
191 ms |
263404 KB |
Output is correct |
14 |
Correct |
176 ms |
263444 KB |
Output is correct |
15 |
Correct |
178 ms |
263528 KB |
Output is correct |
16 |
Correct |
191 ms |
263424 KB |
Output is correct |
17 |
Correct |
172 ms |
263272 KB |
Output is correct |
18 |
Correct |
177 ms |
263360 KB |
Output is correct |
19 |
Correct |
191 ms |
263436 KB |
Output is correct |
20 |
Correct |
168 ms |
263320 KB |
Output is correct |
21 |
Correct |
177 ms |
263424 KB |
Output is correct |
22 |
Correct |
193 ms |
263276 KB |
Output is correct |
23 |
Correct |
175 ms |
263480 KB |
Output is correct |
24 |
Correct |
172 ms |
263236 KB |
Output is correct |
25 |
Correct |
181 ms |
263348 KB |
Output is correct |
26 |
Correct |
171 ms |
262996 KB |
Output is correct |
27 |
Correct |
160 ms |
262964 KB |
Output is correct |
28 |
Correct |
182 ms |
262992 KB |
Output is correct |
29 |
Correct |
1844 ms |
285508 KB |
Output is correct |
30 |
Correct |
1006 ms |
276248 KB |
Output is correct |
31 |
Correct |
2101 ms |
289136 KB |
Output is correct |
32 |
Correct |
1002 ms |
276500 KB |
Output is correct |
33 |
Correct |
2536 ms |
293756 KB |
Output is correct |
34 |
Correct |
1911 ms |
289836 KB |
Output is correct |
35 |
Correct |
2507 ms |
294092 KB |
Output is correct |
36 |
Correct |
1874 ms |
289844 KB |
Output is correct |
37 |
Correct |
951 ms |
274308 KB |
Output is correct |
38 |
Correct |
1259 ms |
278072 KB |
Output is correct |
39 |
Correct |
1930 ms |
286672 KB |
Output is correct |
40 |
Correct |
1944 ms |
286556 KB |
Output is correct |
41 |
Correct |
161 ms |
262988 KB |
Output is correct |
42 |
Correct |
947 ms |
273956 KB |
Output is correct |
43 |
Correct |
1243 ms |
277720 KB |
Output is correct |
44 |
Correct |
1919 ms |
286100 KB |
Output is correct |
45 |
Correct |
1917 ms |
286200 KB |
Output is correct |
46 |
Correct |
2123 ms |
287904 KB |
Output is correct |
47 |
Correct |
307 ms |
266564 KB |
Output is correct |
48 |
Correct |
1109 ms |
278524 KB |
Output is correct |
49 |
Correct |
1585 ms |
283704 KB |
Output is correct |
50 |
Correct |
2719 ms |
309560 KB |
Output is correct |
51 |
Correct |
2793 ms |
319680 KB |
Output is correct |
52 |
Correct |
2800 ms |
319508 KB |
Output is correct |
53 |
Correct |
2800 ms |
319484 KB |
Output is correct |
54 |
Correct |
2789 ms |
319876 KB |
Output is correct |
55 |
Correct |
2620 ms |
319224 KB |
Output is correct |
56 |
Correct |
2736 ms |
319756 KB |
Output is correct |
57 |
Correct |
3017 ms |
319696 KB |
Output is correct |
58 |
Correct |
3356 ms |
319424 KB |
Output is correct |
59 |
Correct |
3314 ms |
319832 KB |
Output is correct |
60 |
Correct |
3260 ms |
319228 KB |
Output is correct |
61 |
Correct |
3341 ms |
319744 KB |
Output is correct |
62 |
Correct |
3420 ms |
319364 KB |
Output is correct |
63 |
Correct |
3351 ms |
318908 KB |
Output is correct |
64 |
Correct |
3252 ms |
316192 KB |
Output is correct |
65 |
Correct |
3403 ms |
316588 KB |
Output is correct |
66 |
Correct |
1429 ms |
289680 KB |
Output is correct |
67 |
Correct |
1663 ms |
293384 KB |
Output is correct |
68 |
Correct |
2003 ms |
297992 KB |
Output is correct |
69 |
Correct |
1794 ms |
295672 KB |
Output is correct |
70 |
Correct |
2495 ms |
322624 KB |
Output is correct |
71 |
Correct |
2571 ms |
322704 KB |
Output is correct |
72 |
Correct |
2557 ms |
322744 KB |
Output is correct |
73 |
Correct |
2591 ms |
322872 KB |
Output is correct |
74 |
Correct |
3352 ms |
333932 KB |
Output is correct |
75 |
Correct |
3277 ms |
339256 KB |
Output is correct |
76 |
Correct |
1853 ms |
300916 KB |
Output is correct |
77 |
Correct |
1794 ms |
298924 KB |
Output is correct |
78 |
Correct |
1794 ms |
299080 KB |
Output is correct |
79 |
Correct |
2659 ms |
322540 KB |
Output is correct |
80 |
Correct |
1859 ms |
298776 KB |
Output is correct |
81 |
Correct |
2714 ms |
322296 KB |
Output is correct |
82 |
Correct |
1850 ms |
299236 KB |
Output is correct |
83 |
Correct |
3127 ms |
322944 KB |
Output is correct |
84 |
Correct |
1821 ms |
298944 KB |
Output is correct |
85 |
Correct |
3216 ms |
323084 KB |
Output is correct |
86 |
Correct |
1816 ms |
290696 KB |
Output is correct |
87 |
Correct |
3257 ms |
323172 KB |
Output is correct |
88 |
Correct |
1789 ms |
299220 KB |
Output is correct |
89 |
Correct |
2606 ms |
313040 KB |
Output is correct |