結果

問題 No.3214 small square
ユーザー jiangxinyang
提出日時 2025-07-25 22:34:33
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,886 bytes
コンパイル時間 2,437 ms
コンパイル使用メモリ 214,764 KB
実行使用メモリ 18,884 KB
最終ジャッジ日時 2025-07-25 22:34:43
合計ジャッジ時間 10,013 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const int N = 200005;
const int INF = 0x3f3f3f3f;
struct SegTree {
    int n;
    struct Node {
        ll mx, tag;
    };
    vector<Node> st;
    SegTree(int _n) : n(_n), st(4 * n + 4, {0, 0}) {}
    void gx(int u, ll v) {
        st[u].mx += v;
        st[u].tag += v;
    }
    void pushdown(int u) {
        if (st[u].tag) {
            gx(u << 1, st[u].tag);
            gx(u << 1 | 1, st[u].tag);
            st[u].tag = 0;
        }
    }
    void pushup(int u) {
        st[u].mx = max(st[u << 1].mx, st[u << 1 | 1].mx);
    }
    void upd(int u, int l, int r, int L, int R, ll v) {
        if (L > r || R < l) return;
        if (L <= l && r <= R) {
            gx(u, v);
            return;
        }
        int mid = l + r >> 1;
        pushdown(u);
        upd(u << 1, l, mid, L, R, v);
        upd(u << 1 | 1, mid + 1, r, L, R, v);
        pushup(u);
    }
    void update(int L, int R, ll v) {
        if (L > R) return;
        upd(1, 0, n - 1, L, R, v);
    }
    ll query(int u, int l, int r, int L, int R) {
        if (L > r || R < l) return 0;
        if (L <= l && r <= R) return st[u].mx;
        int mid = l + r >> 1;
        pushdown(u);
        return max(query(u << 1, l, mid, L, R), query(u << 1 | 1, mid + 1, r, L, R));
    }
    ll query_max() {
        return query(1, 0, n - 1, 0, n - 1);
    }
};
struct Point {
    ll x, y, v;
};
struct Event {
    ll x;
    bool ok;
    int L, R;
    ll d;
};
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    ll A;
    cin >> n >> A;
    vector<Point> pts(n);
    vector<ll> ys;
    ys.reserve(n);
    for (int i = 0; i < n; i++) {
        cin >> pts[i].x >> pts[i].y >> pts[i].v;
        ys.push_back(pts[i].y);
    }
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    int tot = (int)ys.size();
    vector<Event> ev;
    ev.reserve(2 * n);
    for (auto &p : pts) {
        int hi = lower_bound(ys.begin(), ys.end(), p.y) - ys.begin();
        ll ylo = p.y - A;
        int lo = lower_bound(ys.begin(), ys.end(), ylo) - ys.begin();
        ev.push_back({p.x, 0, lo, hi, -p.v});
        ev.push_back({p.x - A, 1, lo, hi, +p.v});
    }
    sort(ev.begin(), ev.end(), [&](auto &a, auto &b) {
        if (a.x != b.x) return a.x < b.x;
        return a.ok > b.ok;
    });
    SegTree st(tot);
    ll ans = 0;
    int i = 0, E = ev.size();
    while (i < E) {
        ll curx = ev[i].x;
        while (i < E && ev[i].x == curx && !ev[i].ok) {
            st.update(ev[i].L, ev[i].R, ev[i].d);
            i++;
        }
        while (i < E && ev[i].x == curx && ev[i].ok) {
            st.update(ev[i].L, ev[i].R, ev[i].d);
            i++;
        }
        ans = max(ans, st.query_max());
    }
    cout << max(ans, 0ll) << "\n";
    return 0;
}
0