#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, L;
int chk[MAX];
pair<int, pii> query[MAX];
struct Node {
ll v, sum;
ll dp[2][2];
ll lz1, lz2;
Node() {
v = sum = 0;
dp[0][0] = dp[1][0] = dp[0][1] = dp[1][1] = -INF;
lz1 = lz2 = 0;
}
};
Node Merge(Node l, Node r) {
Node ret = Node(); ret.v = r.v; ret.sum = l.sum + r.sum + l.v;
for(int i = 0; i <= 1; ++i) for(int j = 0; j <= 1; ++j) {
if(i == 0) ret.dp[i][j] = max(ret.dp[i][j], max(r.dp[0][j], r.dp[1][j]));
if(j == 0) ret.dp[i][j] = max(ret.dp[i][j], max(l.dp[i][0], l.dp[i][1]));
if(i == 1) ret.dp[i][j] = max(ret.dp[i][j], l.sum + r.dp[1][j] + l.v);
if(j == 1) ret.dp[i][j] = max(ret.dp[i][j], l.dp[i][1] + r.sum + l.v);
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) * l.v);
}
}
return ret;
}
Node seg[MAX << 2];
void init(int str, int ed, int node) {
if(str == ed) 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 lazyProp(int str, int ed, int node) {
if(seg[node].lz1) {
seg[node].sum += seg[node].lz1;
for(int i = 0; i <= 1; ++i) for(int j = 0; j <= 1; ++j) seg[node].dp[i][j] += seg[node].lz1;
if(str != ed) {
seg[node << 1].lz1 += seg[node].lz1;
seg[node << 1 | 1].lz1 += seg[node].lz1;
}
seg[node].lz1 = 0;
}
if(seg[node].lz2) {
seg[node].v += seg[node].lz2;
if(str != ed) {
seg[node << 1].lz2 += seg[node].lz2;
seg[node << 1 | 1].lz2 += seg[node].lz2;
}
seg[node].lz2 = 0;
}
}
void update1(int str, int ed, int left, int right, ll val, int node) {
lazyProp(str, ed, node);
if(str > right || ed < left) return;
if(left <= str && ed <= right) {
seg[node].lz1 = val;
lazyProp(str, ed, node);
return;
}
int mid = str + ed >> 1;
update1(str, mid, left, right, val, node << 1);
update1(mid + 1, ed, left, right, val, node << 1 | 1);
seg[node] = Merge(seg[node << 1], seg[node << 1 | 1]);
}
void update2(int str, int ed, int left, int right, ll val, int node) {
lazyProp(str, ed, node);
if(str > right || ed < left) return;
if(left <= str && ed <= right) {
seg[node].lz2 = val;
lazyProp(str, ed, node);
return;
}
int mid = str + ed >> 1;
update2(str, mid, left, right, val, node << 1);
update2(mid + 1, ed, left, right, val, node << 1 | 1);
seg[node] = Merge(seg[node << 1], seg[node << 1 | 1]);
}
void update3(int str, int ed, int idx, ll val, int node) {
lazyProp(str, ed, node);
if(str > idx || ed < idx) return;
if(str == ed) {
seg[node].dp[1][1] += val;
return;
}
int mid = str + ed >> 1;
update3(str, mid, idx, val, node << 1);
update3(mid + 1, ed, idx, val, node << 1 | 1);
seg[node] = Merge(seg[node << 1], seg[node << 1 | 1]);
}
ll max_query(int str, int ed, int node) {
lazyProp(str, ed, node);
return max(0ll, max(seg[1].dp[0][0]);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> q >> L;
for(int i = 1; i <= q; ++i) cin >> query[i].first >> query[i].second.first >> query[i].second.second;
vector<int> tmp; tmp.push_back(-1000000005); tmp.push_back(2000000005);
for(int i = 1; i <= q; ++i) if(query[i].first == 1) tmp.push_back(query[i].second.first);
sort(tmp.begin(), tmp.end()); tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
int n = tmp.size() - 1;
init(0, n, 1); ll A = 0, B = 0;
for(int i = 1; i <= q; ++i) {
if(query[i].first == 1) {
int idx = lower_bound(tmp.begin(), tmp.end(), query[i].second.first) - tmp.begin();
A += query[i].second.second;
if(chk[idx] == 0) chk[idx] = 1, update3(0, n, idx, 1ll * query[i].second.second + INF, 1);
else update3(0, n, idx, query[i].second.second, 1);
}
else {
int l = lower_bound(tmp.begin(), tmp.end(), query[i].second.first - L) - tmp.begin();
int r = upper_bound(tmp.begin(), tmp.end(), query[i].second.first + L) - tmp.begin() - 1;
B += query[i].second.second;
if(l <= r) update1(0, n, l, r, -query[i].second.second, 1);
if(l < r) update2(0, n, l, r - 1, query[i].second.second, 1);
}
cout << A - max_query(0, n, 1) << '\n';
}
return 0;
}
Compilation message
sugar.cpp: In function 'void init(int, int, int)':
sugar.cpp:48:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
48 | int mid = str + ed >> 1;
| ~~~~^~~~
sugar.cpp: In function 'void update1(int, int, int, int, ll, int)':
sugar.cpp:83:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
83 | int mid = str + ed >> 1;
| ~~~~^~~~
sugar.cpp: In function 'void update2(int, int, int, int, ll, int)':
sugar.cpp:97:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
97 | int mid = str + ed >> 1;
| ~~~~^~~~
sugar.cpp: In function 'void update3(int, int, int, ll, int)':
sugar.cpp:110:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
110 | int mid = str + ed >> 1;
| ~~~~^~~~
sugar.cpp: In function 'll max_query(int, int, int)':
sugar.cpp:118:40: error: no matching function for call to 'max(ll&)'
118 | return max(0ll, max(seg[1].dp[0][0]);
| ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from sugar.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
sugar.cpp:118:40: note: candidate expects 2 arguments, 1 provided
118 | return max(0ll, max(seg[1].dp[0][0]);
| ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from sugar.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
300 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: template argument deduction/substitution failed:
sugar.cpp:118:40: note: candidate expects 3 arguments, 1 provided
118 | return max(0ll, max(seg[1].dp[0][0]);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from sugar.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
3480 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: template argument deduction/substitution failed:
sugar.cpp:118:40: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
118 | return max(0ll, max(seg[1].dp[0][0]);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from sugar.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
3486 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: template argument deduction/substitution failed:
sugar.cpp:118:40: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
118 | return max(0ll, max(seg[1].dp[0][0]);
| ^
