This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define MAX 500005
#define MOD 998244353
#define INF (ll)(1e18)
#define inf (1987654321)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef complex<long double> cpx;
constexpr long double PI = acos(-1);
int q;
ll L;
ll arr[MAX];
struct Node {
int s, e;
ll dp[2][2];
Node() { dp[0][0] = dp[1][0] = dp[0][1] = dp[1][1] = -INF; }
};
Node Merge(Node l, Node r) {
Node ret = Node();
ret.s = l.s, ret.e = r.e;
for(int i = 0; i <= 1; ++i) for(int j = 0; j <= 1; ++j) {
for(int a = 0; a <= 1; ++a) for(int b = 0; b <= 1; ++b) {
ret.dp[i][j] = max(ret.dp[i][j], l.dp[i][a] + r.dp[b][j] - (a | b) * arr[2 * l.e]);
}
}
return ret;
}
Node seg[MAX << 2];
void init(int str, int ed, int node) {
if(str == ed) {
seg[node].s = seg[node].e = str;
seg[node].dp[0][0] = seg[node].dp[1][1] = 0;
seg[node].dp[0][1] = seg[node].dp[1][0] = -INF;
return;
}
int mid = str + ed >>1;
init(str, mid, node << 1);
init(mid + 1, ed, node << 1 | 1);
seg[node] = Merge(seg[node << 1], seg[node << 1 | 1]);
}
void update(int str, int ed, int idx, int node) {
if(str == ed){
seg[node].dp[1][1] = arr[2 * str - 1];
return;
}
int mid = str + ed >> 1;
if(idx <= mid) update(str, mid, idx, node << 1);
else update(mid + 1, ed, idx, node << 1 | 1);
seg[node] = Merge(seg[node << 1], seg[node << 1 | 1]);
}
void print(int str, int ed, int node) {
cout << str << ' ' << ed << " : " << seg[node].dp[0][0] << ' ' << seg[node].dp[1][0] << ' ' << seg[node].dp[0][1] << ' ' << seg[node].dp[1][1] << endl;
if(str == ed) return;
int mid = str + ed >> 1;
print(str, mid, node << 1);
print(mid + 1, ed, node << 1 | 1);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> q >> L;
init(0, q/2, 1);
ll A = 0;
for(int tt = 1; tt <= q; ++tt) {
int t, x, v; cin >> t >> x >> v;
arr[x] += v;
if(t == 1) A += v, update(0, q/2, (x + 1)/2, 1);
else update(0, q/2, x/2, 1);
cout << A - max(max(seg[1].dp[0][0], seg[1].dp[0][1]), max(seg[1].dp[1][0], seg[1].dp[1][1])) << '\n';
// print(0, q/2, 1);
// cout << endl;
}
return 0;
}
Compilation message (stderr)
sugar.cpp: In function 'void init(int, int, int)':
sugar.cpp:43:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | int mid = str + ed >>1;
| ~~~~^~~~
sugar.cpp: In function 'void update(int, int, int, int)':
sugar.cpp:54:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
54 | int mid = str + ed >> 1;
| ~~~~^~~~
sugar.cpp: In function 'void print(int, int, int)':
sugar.cpp:63:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
63 | int mid = str + ed >> 1;
| ~~~~^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |