結果

問題 No.3214 small square
ユーザー jiangxinyang
提出日時 2025-07-25 22:22:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,583 bytes
コンパイル時間 2,139 ms
コンパイル使用メモリ 214,644 KB
実行使用メモリ 21,836 KB
最終ジャッジ日時 2025-07-25 22:22:25
合計ジャッジ時間 9,574 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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;
#define int long long
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) return;
        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 x, int y, ll v) {
        if (x <= l && r <= y) {
            gx(u, v);
            return;
        }
        int mid = l + r >> 1;
        pushdown(u);
        if (x <= mid) upd(u << 1, l, mid, x, y, v);
        if (y > mid) upd(u << 1 | 1, mid + 1, r, x, y, v);
        pushup(u);
    }
    void update(int L, int R, ll v) {
        if (L > R) return;
        upd(1, 0, n - 1, L, R, v);
    }
};
struct point {
    ll x, y, v;
};
struct Qode {
    ll x;
    bool ok;
    int L, R;
    ll d;
};
signed 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> vy;
    vy.reserve(n);
    for (int i = 0; i < n; i++) {
        cin >> pts[i].x >> pts[i].y >> pts[i].v;
        vy.push_back(pts[i].y);
    }
    sort(vy.begin(), vy.end());
    vy.erase(unique(vy.begin(), vy.end()), vy.end());
    int tot = (int)vy.size();
    vector<Qode> ev;
    for (auto &p : pts) {
        int yi = lower_bound(vy.begin(), vy.end(), p.y) - vy.begin();
        ll L = p.y - A;
        int lo = lower_bound(vy.begin(), vy.end(), L) - vy.begin();
        int R = yi;
        ev.push_back({p.x - A, 1, lo, R, p.v});
        ev.push_back({p.x, 0, lo, R, -p.v});
    }
    sort(ev.begin(), ev.end(), [&](auto &x, auto &y) {
        if (x.x != y.x) return x.x < y.x;
        return x.ok > y.ok;
    });
    SegTree st(tot);
    ll ans = 0;
    int i = 0;
    while (i < (int)ev.size()) {
        ll curx = ev[i].x;
        while (i < (int)ev.size() && ev[i].x == curx && ev[i].ok) {
            st.update(ev[i].L, ev[i].R, ev[i].d);
            i++;
        }
        ans = max(ans, st.st[1].mx);
        while (i < (int)ev.size() && ev[i].x == curx && !ev[i].ok) {
            st.update(ev[i].L, ev[i].R, ev[i].d);
            i++;
        }
        ans = max(ans, st.st[1].mx);
    }
    cout << max(ans, 0ll) << "\n";
    return 0;
}
0