#include<bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
using namespace std;
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int q, L;
cin >> q >> L;
vector<int> cnt(500500);
vector<int> mx(500500);
int ans = 0;
vector<int> Q1(q), Q2(q);
vector<vector<int>> ss;
for (int i = 0; i < q; ++i) {
int t, x, a;
cin >> t >> x >> a;
ss.push_back({t, x, a});
x += 11;
if (x % 2 == 1) {
ans -= min(cnt[x], cnt[x + 1]);
cnt[x] += a;
ans += min(cnt[x], cnt[x + 1]);
}
else {
ans -= min(cnt[x], cnt[x - 1]);
cnt[x] += a;
ans += min(cnt[x], cnt[x - 1]);
}
if (x % 2 == 1) {
ans -= min(mx[x + 3], mx[x + 4]);
ans -= min(mx[x + 1], mx[x + 2]);
ans -= min(mx[x - 1], mx[x]);
ans -= min(mx[x - 3], mx[x - 1]);
mx[x] = max(0ll, cnt[x] - cnt[x + 1]);
mx[x + 1] = max(0ll, cnt[x + 1] - cnt[x]);
ans += min(mx[x + 3], mx[x + 4]);
ans += min(mx[x + 1], mx[x + 2]);
ans += min(mx[x - 1], mx[x]);
ans += min(mx[x - 3], mx[x - 1]);
}
else {
ans -= min(mx[x + 2], mx[x + 3]);
ans -= min(mx[x], mx[x + 1]);
ans -= min(mx[x - 2], mx[x - 1]);
ans -= min(mx[x - 4], mx[x - 2]);
mx[x] = max(0ll, cnt[x] - cnt[x - 1]);
mx[x - 1] = max(0ll, cnt[x - 1] - cnt[x]);
ans += min(mx[x + 2], mx[x + 3]);
ans += min(mx[x], mx[x + 1]);
ans += min(mx[x - 2], mx[x - 1]);
ans += min(mx[x - 4], mx[x - 2]);
}
Q1[i] = ans;
}
fill(cnt.begin(), cnt.end(), 0);
fill(mx.begin(), mx.end(), 0);
ans = 0;
for (int i = 0; i < q; ++i) {
int t, x, a;
t = ss[i][0];
x = ss[i][1];
a = ss[i][2];
x += 9;
if (x % 2 == 1) {
ans -= min(cnt[x], cnt[x + 1]);
cnt[x] += a;
ans += min(cnt[x], cnt[x + 1]);
}
else {
ans -= min(cnt[x], cnt[x - 1]);
cnt[x] += a;
ans += min(cnt[x], cnt[x - 1]);
}
if (x % 2 == 1) {
ans -= min(mx[x + 3], mx[x + 4]);
ans -= min(mx[x + 1], mx[x + 2]);
ans -= min(mx[x - 1], mx[x]);
ans -= min(mx[x - 3], mx[x - 1]);
mx[x] = max(0ll, cnt[x] - cnt[x + 1]);
mx[x + 1] = max(0ll, cnt[x + 1] - cnt[x]);
ans += min(mx[x + 3], mx[x + 4]);
ans += min(mx[x + 1], mx[x + 2]);
ans += min(mx[x - 1], mx[x]);
ans += min(mx[x - 3], mx[x - 1]);
}
else {
ans -= min(mx[x + 2], mx[x + 3]);
ans -= min(mx[x], mx[x + 1]);
ans -= min(mx[x - 2], mx[x - 1]);
ans -= min(mx[x - 4], mx[x - 2]);
mx[x] = max(0ll, cnt[x] - cnt[x - 1]);
mx[x - 1] = max(0ll, cnt[x - 1] - cnt[x]);
ans += min(mx[x + 2], mx[x + 3]);
ans += min(mx[x], mx[x + 1]);
ans += min(mx[x - 2], mx[x - 1]);
ans += min(mx[x - 4], mx[x - 2]);
}
Q2[i] = ans;
}
for (int i = 0; i < q; ++i) {
cout << max(Q1[i], Q2[i]) << '\n';
}
}
Compilation message
sugar.cpp: In function 'int main()':
sugar.cpp:66:13: warning: variable 't' set but not used [-Wunused-but-set-variable]
66 | int t, x, a;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
8148 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
8148 KB |
Output is correct |
| 2 |
Correct |
3 ms |
8148 KB |
Output is correct |
| 3 |
Correct |
3 ms |
8148 KB |
Output is correct |
| 4 |
Incorrect |
137 ms |
38956 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
16308 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
8148 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
