#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll INF = 4e18;
struct P{
ll x;
int c;
P(){}
P(ll _x, int _c): x(_x), c(_c) {}
bool operator < (const P &p) const{return x < p.x;}
P operator + (const P &p) const{return P(x + p.x, c + p.c);}
};
struct Node{
P ans[2][2];
ll one[2][2];
Node(){}
Node(ll c, ll d){
ans[0][0] = P(-c, 0);
ans[0][1] = P(-INF, 0);
ans[1][0] = P(-INF, 0);
ans[1][1] = P(d, 1);
one[0][0] = -c;
one[0][1] = -INF;
one[1][0] = -INF;
one[1][1] = d;
}
void pcd(ll x){
ans[0][0].x -= x;
ans[1][1].x += x;
one[0][0] -= x;
one[1][1] += x;
}
void pd(ll x){
assert(x<0);
one[0][1] += x;
one[1][0] += x;
one[1][1] += x;
for (int i=0;i<2;i++){
for (int j=0;j<2;j++){
assert(ans[i][j].c <= 2);
ans[i][j].x += x * ans[i][j].c;
if (ans[i][j].x < one[i][j]){
ans[i][j].x = one[i][j];
if (i || j) ans[i][j].c = 1;
else ans[i][j].c = 0;
}
}
}
}
Node operator + (const Node &N) const{
Node ret;
for (int i=0;i<2;i++){
for (int j=0;j<2;j++){
ret.ans[i][j] = max(ans[i][j], N.ans[i][j]);
ret.one[i][j] = max(one[i][j], N.one[i][j]);
for (int k=0;k<2;k++) ret.ans[i][j] = max(ret.ans[i][j], ans[i][k] + N.ans[k^1][j]);
}
}
ret.one[0][1] = max(ret.one[0][1], one[0][0] + N.one[1][1]);
ret.one[1][0] = max(ret.one[1][0], one[1][1] + N.one[0][0]);
return ret;
}
};
struct Seg{
Node tree[1101000];
pair<ll, ll> lazy[1101000];
void init(int i, int l, int r){
lazy[i] = {0, 0};
if (l==r) {tree[i] = Node(0, 0); return;}
int m = (l+r)>>1;
init(i<<1, l, m); init(i<<1|1, m+1, r);
tree[i] = tree[i<<1] + tree[i<<1|1];
}
void propagate(int i, int l, int r){
if (lazy[i].first) tree[i].pcd(lazy[i].first);
if (lazy[i].second) tree[i].pd(lazy[i].second);
if (l!=r){
lazy[i<<1].first += lazy[i].first;
lazy[i<<1].second += lazy[i].second;
lazy[i<<1|1].first += lazy[i].first;
lazy[i<<1|1].second += lazy[i].second;
}
lazy[i] = {0, 0};
}
void update1(int i, int l, int r, int s, int e, ll x){
propagate(i, l, r);
if (r<s || e<l) return;
if (s<=l && r<=e){
lazy[i].first += x;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update1(i<<1, l, m, s, e, x); update1(i<<1|1, m+1, r, s, e, x);
tree[i] = tree[i<<1] + tree[i<<1|1];
}
void update2(int i, int l, int r, int s, int e, ll x){
propagate(i, l, r);
if (r<s || e<l) return;
if (s<=l && r<=e){
lazy[i].second += x;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update2(i<<1, l, m, s, e, x); update2(i<<1|1, m+1, r, s, e, x);
tree[i] = tree[i<<1] + tree[i<<1|1];
}
}tree;
vector<int> C[3];
int T[500500], X[500500], A[500500], d;
int main(){
int q;
scanf("%d %d", &q, &d);
for (int i=1;i<=q;i++){
scanf("%d %d %d", T+i, X+i, A+i);
C[T[i]].push_back(X[i]);
C[T[i]].push_back(X[i]-1);
}
for (int k=0;k<2;k++){
C[k].push_back(0);
sort(C[k].begin(), C[k].end());
C[k].erase(unique(C[k].begin(), C[k].end()), C[k].end());
}
int ant = C[1].size()<C[2].size()?1:2;
int sz = C[ant].size();
tree.init(1, 1, sz);
ll cur = 0;
for (int i=1;i<=q;i++){
if (T[i]==ant){
int idx = lower_bound(C[ant].begin(), C[ant].end(), X[i]) - C[ant].begin() + 1;
tree.update1(1, 1, sz, idx, sz, A[i]);
cur += A[i];
}
else{
int idx1 = lower_bound(C[ant].begin(), C[ant].end(), X[i]-d) - C[ant].begin() + 1;
int idx2 = lower_bound(C[ant].begin(), C[ant].end(), X[i]+d) - C[ant].begin() + 1;
tree.update1(1, 1, sz, idx2, sz, -A[i]);
tree.update2(1, 1, sz, idx1, idx2-1, -A[i]);
}
ll ans = cur - max(tree.tree[1].ans[0][1].x, 0LL);
printf("%lld\n", ans);
}
return 0;
}
Compilation message
sugar.cpp: In function 'int main()':
sugar.cpp:133:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
133 | scanf("%d %d", &q, &d);
| ~~~~~^~~~~~~~~~~~~~~~~
sugar.cpp:135:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
135 | scanf("%d %d %d", T+i, X+i, A+i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
17492 KB |
Output is correct |
| 2 |
Correct |
8 ms |
17492 KB |
Output is correct |
| 3 |
Correct |
7 ms |
17492 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
17492 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
17492 KB |
Output is correct |
| 2 |
Correct |
7 ms |
17492 KB |
Output is correct |
| 3 |
Correct |
7 ms |
17472 KB |
Output is correct |
| 4 |
Correct |
1109 ms |
79360 KB |
Output is correct |
| 5 |
Correct |
512 ms |
75268 KB |
Output is correct |
| 6 |
Correct |
1334 ms |
100640 KB |
Output is correct |
| 7 |
Incorrect |
401 ms |
75392 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
17492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
17492 KB |
Output is correct |
| 2 |
Correct |
8 ms |
17492 KB |
Output is correct |
| 3 |
Correct |
7 ms |
17492 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
17492 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
