結果

問題 No.3214 small square
コンテスト
ユーザー detteiuu
提出日時 2025-07-25 23:21:03
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,786 ms / 3,000 ms
コード長 2,674 bytes
コンパイル時間 3,838 ms
コンパイル使用メモリ 308,408 KB
実行使用メモリ 88,908 KB
最終ジャッジ日時 2025-07-25 23:21:58
合計ジャッジ時間 49,646 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/lazysegtree>
using namespace std;
using namespace atcoder;

using ll = long long;
const ll INF = 1LL << 60;

// 区間加算・区間最大値取得
ll op(ll a, ll b){ return max(a, b); }
ll e(){ return -INF; }
ll mapping(ll f, ll x){ return f+x; }
ll composition(ll f, ll g){ return f+g; }
ll id(){ return 0; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    ll A;
    cin >> N >> A;
    vector<tuple<ll, ll, ll>> P(N);
    for (int i = 0; i < N; i++) {
        ll x, y, v;
        cin >> x >> y >> v;
        P[i] = {x, y, v};
    }

    sort(P.begin(), P.end());

    auto compress = [](vector<ll> &vec) {
        vector<ll> S = vec;
        sort(S.begin(), S.end());
        S.erase(unique(S.begin(), S.end()), S.end());
        map<ll, int> D;
        for (int i = 0; i < (int)S.size(); i++) {
            D[S[i]] = i;
        }
        return make_pair(D, S);
    };

    auto func = [&](ll B) {
        vector<ll> X, Y;
        for (auto &[x, y, v] : P) {
            X.push_back(x + B);
            X.push_back(x);
            X.push_back(x + B + 1);
            X.push_back(x - 1);

            Y.push_back(y);
            Y.push_back(y - A);
            Y.push_back(y - (A - 1));
            Y.push_back(y + 1);
            Y.push_back(y - A - 1);
            Y.push_back(y - (A - 1) - 1);
        }

        sort(X.begin(), X.end());
        X.erase(unique(X.begin(), X.end()), X.end());

        auto [D, C] = compress(Y);
        int M = C.size();

        vector<int> L1(M), L2(M);
        for (int i = 0; i < M; i++) {
            L1[i] = lower_bound(C.begin(), C.end(), C[i] - A) - C.begin();
            L2[i] = lower_bound(C.begin(), C.end(), C[i] - (A - 1)) - C.begin();
        }

        vector<ll> def(M, 0);
        lazy_segtree<ll, op, e, ll, mapping, composition, id> seg1(def), seg2(def);

        int idxR = 0, idxL = 0;
        ll ans = 0;
        for (ll x : X) {
            while (idxR < N && get<0>(P[idxR]) <= x) {
                auto &[_, y, v] = P[idxR];
                int dy = D[y];
                seg1.apply(L1[dy], dy + 1, v);
                seg2.apply(L2[dy], dy + 1, v);
                idxR++;
            }
            while (idxL < N && get<0>(P[idxL]) < x - B) {
                auto &[_, y, v] = P[idxL];
                int dy = D[y];
                seg1.apply(L1[dy], dy + 1, -v);
                seg2.apply(L2[dy], dy + 1, -v);
                idxL++;
            }
            ans = max({ans, seg1.all_prod(), seg2.all_prod()});
        }

        return ans;
    };

    cout << max({func(A), func(A - 1), 0LL}) << '\n';

    return 0;
}
0