// ~ Be Name Khoda ~
#include <bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 5e5 + 10;
const int maxn5 = 5e5 + 10;
const int maxnt = 2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const int lg = 19;
const ll inf = 1e18;
int lim, m, lef[maxn5], rig[maxn5], a[maxn5], ty[maxn5];
int segl[maxnt][2][2], segr[maxnt][2][2], x[maxn5];
ll dp[maxnt][2][2];
vector <int> av;
struct segmnt_tree{
pair <ll, int> mx[maxnt][2];
ll lazy[maxnt][2];
void build(int l, int r, int v){
mx[v][0] = mx[v][1] = {0, l};
if(r - l == 1)
return;
int mid = (l + r) >> 1;
build(l, mid, v * 2);
build(mid, r, v * 2 + 1);
}
void add(int l, int r, int lq, int rq, int val, int ty, int v){
if(rq <= l || r <= lq)
return;
if(lq <= l && r <= rq){
lazy[v][ty] += val;
mx[v][ty].fi += val;
return;
}
int mid = (l + r) >> 1;
add(l, mid, lq, rq, val, ty, v * 2);
add(mid, r, lq, rq, val, ty, v * 2 + 1);
mx[v][ty] = max(mx[v * 2][ty], mx[v * 2 + 1][ty]);
mx[v][ty].fi += lazy[v][ty];
}
pair <ll, int> get_max(int l, int r, int lq, int rq, int ty, int v){
if(rq <= l || r <= lq)
return {-inf, 0};
if(lq <= l && r <= rq)
return mx[v][ty];
int mid = (l + r) >> 1;
auto ans = max(get_max(l, mid, lq, rq, ty, v * 2), get_max(mid, r, lq, rq, ty, v * 2 + 1));
return {ans.fi + lazy[v][ty], ans.se};
}
} seg[lg];
void add(int l, int r, int id, int val, int ty, int v, int h){
if(r - l == 1){
dp[v][ty][ty] += val;
return;
}
int mid = (l + r) >> 1;
if(id < mid){
add(l, mid, id, val, ty, v * 2, h + 1);
seg[h].add(0, m, l, id, -val, ty, 1);
}
else{
add(mid, r, id, val, ty, v * 2 + 1, h + 1);
seg[h].add(0, m, lef[id], mid, -val, ty ^ 1, 1);
}
for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++){
ll val1 = dp[v * 2][i][0] + dp[v * 2 + 1][0][j], val2 = dp[v * 2][i][1] + dp[v * 2 + 1][1][j];
ll val3 = -inf, val4 = -inf;
int ind1, ind2;
if(rig[segr[v * 2][i][0]] < segl[v * 2 + 1][1][j]){
auto ans = seg[h].get_max(0, m, segr[v * 2][i][0], min(mid, lef[segl[v * 2 + 1][1][j]]), 0, 1);
val3 = dp[v * 2][i][0] + dp[v * 2 + 1][1][j] + ans.fi;
ind1 = ans.se;
}
if(rig[segr[v * 2][i][1]] < segl[v * 2 + 1][0][j]){
auto ans = seg[h].get_max(0, m, segr[v * 2][i][1], min(mid, lef[segl[v * 2 + 1][0][j]]), 1, 1);
val4 = dp[v * 2][i][1] + dp[v * 2 + 1][0][j] + ans.fi;
//cout << "hmm " << ans.fi << ' ' << ans.se << '\n';
ind2 = ans.se;
}
dp[v][i][j] = max({val1, val2, val3, val4});
if(val1 >= max({val2, val3, val4})){
segl[v][i][j] = segl[v * 2][i][0];
segr[v][i][j] = segr[v * 2 + 1][0][j];
if(segl[v * 2][i][0] == mid - 1)
segl[v][i][j] = segl[v * 2 + 1][0][j];
if(segr[v * 2 + 1][0][j] == mid)
segr[v][i][j] = segr[v * 2][i][0];
}
else if(val2 >= max(val3, val4)){
segl[v][i][j] = segl[v * 2][i][1];
segr[v][i][j] = segr[v * 2 + 1][1][j];
if(segl[v * 2][i][1] == mid - 1)
segl[v][i][j] = segl[v * 2 + 1][1][j];
if(segr[v * 2 + 1][1][j] == mid)
segr[v][i][j] = segr[v * 2][i][1];
}
else if(val3 > val4){
segl[v][i][j] = segl[v * 2][i][0];
segr[v][i][j] = segr[v * 2 + 1][1][j];
if(segl[v * 2][i][0] == mid - 1)
segl[v][i][j] = ind1;
if(segr[v * 2 + 1][1][j] == mid)
segr[v][i][j] = rig[ind1] + 1;
}
else{
segl[v][i][j] = segl[v * 2][i][1];
segr[v][i][j] = segr[v * 2 + 1][0][j];
if(segl[v * 2][i][1] == mid - 1)
segl[v][i][j] = ind2;
if(segr[v * 2 + 1][0][j] == mid)
segr[v][i][j] = rig[ind2] + 1;
}
/*
cout << "well done " << l << ' ' << r << ' ' << id << ' ' << v << ' ' << i << ' ' << j << ' ' << dp[v][i][j];
cout << ' ' << val1 << ' ' << val2 << ' ' << val3 << ' ' << val4 << '\n';
cout << segl[v][i][j] << ' ' << segr[v][i][j] << '\n';
//*/
}
return;
}
void build(int l, int r, int v){
segl[v][0][0] = segl[v][1][1] = r - 1;
segr[v][0][0] = segr[v][1][1] = l;
dp[v][0][1] = dp[v][1][0] = -inf;
if(r - l == 1)
return;
int mid = (l + r) >> 1;
build(l, mid, v * 2);
build(mid, r, v * 2 + 1);
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
int n; cin >> n >> lim;
for(int i = 0; i < n; i++){
cin >> ty[i] >> x[i] >> a[i];
ty[i]--;
av.pb(x[i]);
}
sort(all(av));
av.resize(unique(all(av)) - av.begin());
m = av.size();
for(int i = 0; i < lg; i++)
seg[i].build(0, m, 1);
build(0, m, 1);
for(int i = 0; i < m; i++){
lef[i] = lower_bound(all(av), av[i] - lim) - av.begin();
rig[i] = upper_bound(all(av), av[i] + lim) - av.begin() - 1;
}
ll sum = 0;
for(int i = 0; i < n; i++){
sum += a[i];
int pt = lower_bound(all(av), x[i]) - av.begin();
add(0, m, pt, a[i], ty[i], 1, 0);
cout << sum - max({dp[1][0][0], dp[1][1][0], dp[1][1][1], dp[1][0][1]}) << '\n';
}
}
/*
6 6
2 27 12
2 9 11
1 36 10
2 39 4
2 14 9
2 33 7
2 38 20
2 0 20
2 25 16
1 14 3
1 13 19
2 6 4
2 15 6
2 33 4
1 12 11
1 44 1
2 17 14
2 12 19
1 48 18
2 30 16
*/
Compilation message
sugar.cpp: In function 'void add(int, int, int, int, int, int, int)':
sugar.cpp:133:41: warning: 'ind2' may be used uninitialized in this function [-Wmaybe-uninitialized]
133 | segr[v][i][j] = rig[ind2] + 1;
| ~~~~~~~~^
sugar.cpp:125:41: warning: 'ind1' may be used uninitialized in this function [-Wmaybe-uninitialized]
125 | segr[v][i][j] = rig[ind1] + 1;
| ~~~~~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
491 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
398 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
385 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
491 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
