#include <iostream>
#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
template <class Info, class Tag>
struct ImplicitLazySegmentTree {
struct Node {
Info info = Info();
Tag tag = Tag();
int ln = 0, rn = 0;
};
ll n;
vector<Node> nodes;
ImplicitLazySegmentTree(ll n) : n(n), nodes(2) {
nodes[1].info.makeDefault(0, n);
}
void apply(int p, const Tag &t) {
nodes[p].info.apply(t);
nodes[p].tag.apply(t);
}
void pull(int p) {
nodes[p].info = nodes[nodes[p].ln].info + nodes[nodes[p].rn].info;
}
void push(int p) {
apply(nodes[p].ln, nodes[p].tag);
apply(nodes[p].rn, nodes[p].tag);
nodes[p].tag = Tag();
}
void newNode(int &aug, int l, int r) {
aug = nodes.size();
nodes.push_back(nodes[0]);
nodes.back().info.makeDefault(l, r);
}
template <class T>
void modify(int i, const T &val) {
auto dfs = [&](auto self, int p, int l, int r) -> void {
if (l + 1 == r) {
nodes[p].info = val;
return;
}
int m = (l + r) >> 1;
if (nodes[p].ln == 0) newNode(nodes[p].ln, l, m);
if (nodes[p].rn == 0) newNode(nodes[p].rn, m, r);
push(p);
if (i < m) self(self, nodes[p].ln, l, m);
else self(self, nodes[p].rn, m, r);
pull(p);
};
dfs(dfs, 1, 0, n);
}
void rangeApply(int ql, int qr, const Tag &t) {
auto dfs = [&](auto self, int p, int l, int r) -> void {
if (r <= ql || qr <= l) return;
if (ql <= l && r <= qr) return apply(p, t);
int m = (l + r) >> 1;
if (nodes[p].ln == 0) newNode(nodes[p].ln, l, m);
if (nodes[p].rn == 0) newNode(nodes[p].rn, m, r);
push(p);
self(self, nodes[p].ln, l, m);
self(self, nodes[p].rn, m, r);
pull(p);
};
dfs(dfs, 1, 0, n);
}
Info rangeQuery(int ql, int qr) {
Info res = Info();
auto dfs = [&](auto self, int p, int l, int r, Tag t) -> void {
if (r <= ql || qr <= l) return;
if (ql <= l && r <= qr) {
Info info = nodes[p].info;
if (p == 0) info.makeDefault(l, r);
info.apply(t);
res = res + info;
return;
}
int m = (l + r) >> 1;
t.apply(nodes[p].tag);
self(self, nodes[p].ln, l, m, t);
self(self, nodes[p].rn, m, r, t);
};
dfs(dfs, 1, 0, n, Tag());
return res;
}
template <class F>
int findFirst(int ql, int qr, F &&pred) {
Info res = Info();
auto dfs = [&](auto self, int p, int l, int r, Tag t) -> int {
if (r <= ql || qr <= l) return -1;
Info info = nodes[p].info;
if (p == 0) info.makeDefault(l, r);
info.apply(t);
if (ql <= l && r <= qr && !pred(info)) return -1;
if (l + 1 == r) return l;
int m = (l + r) >> 1;
t.apply(nodes[p].tag);
int get = self(self, nodes[p].ln, l, m, t);
if (get == -1) get = self(self, nodes[p].rn, m, r, t);
return get;
};
return dfs(dfs, 1, 0, n, Tag());
}
};
struct Tag {
ll add = 0;
void apply(const Tag &t) {
add += t.add;
}
};
struct Info2 {
ll sum = 0;
void makeDefault(int l, int r) {}
void apply(const Tag &t) {
sum += t.add;
}
Info2 operator+(const Info2 &b) const {
return {sum + b.sum};
}
};
struct Info {
ll f[2][2] = {{0, INF}, {INF, INF}};
ll b = 0;
bool is_I = true;
void makeDefault(int l, int r) {is_I = false;}
void apply(const Tag &t) {
}
Info operator+(const Info &b) const {
Info a = *this, res;
if(a.is_I) return b;
if(b.is_I) return a;
res.is_I = false;
res.b = a.b + b.b;
for(int i = 0; i <= 1; i++){
for(int j = 0; j <= 1; j++){
for(int k = 0; k <= 1; k++){
res.f[i][j] = min(res.f[i][j], a.f[i][k] + b.f[k][j]);
}
}
}
res.f[1][0] = min(res.f[1][0], a.b + b.f[1][0]);
res.f[0][1] = min(res.f[0][1], a.f[0][1] + b.b);
res.f[1][1] = min({res.f[1][1], a.f[1][1] + b.b, b.f[1][1] + a.b});
return res;
}
};
void solve(){
int q, L;
cin >> q >> L;
ll N = 2e9;
ImplicitLazySegmentTree<Info, Tag> T(N+1);
ImplicitLazySegmentTree<Info2, Tag> Tb(N+1);
map<int, ll> Ta;
ll sumV1 = 0;
for(int i = 1; i <= q; i++){
ll t, x, a;
cin >> t >> x >> a;
if(t == 1){
Tb.rangeApply(x, x+1, {a});
Info I;
I.is_I = false;
I.b = Tb.rangeQuery(x, x+1).sum;
T.modify(x, I);
cout << 0 << "\n";
}else{
Ta[x] += a;
sumV1 += a;
Info I;
I.is_I = false;
ll A = Ta[x];
I.b = -A + Tb.rangeQuery(x, x+1).sum;
I.f[0][0] = min(0LL, -A + Tb.rangeQuery(max(0LL, x-L), min(N+1, x+L+1)).sum);
I.f[1][0] = -A + Tb.rangeQuery(x, min(N+1, x+L+1)).sum;
I.f[0][1] = -A + Tb.rangeQuery(max(0LL, x-L), x+1).sum;
T.modify(x, I);
cout << sumV1 + T.rangeQuery(0, N+1).f[0][0] << "\n";
}
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen("main.inp", "r", stdin);
//freopen("main.out", "w", stdout);
solve();
}
# | 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... |