読者です 読者をやめる 読者になる 読者になる

AOJ 0302 Star Watching

解法

星を輝度でソートする.
輝度の最小(つまり左端)を決めて,しゃくとり法でできる.
座標の最大最小は,priority_queueでもmapでもmultisetでもなんでもよい.
自分は最初 priority_queue で書いて通したが,他の人のコードを読むと multiset が一番すっきりしていたのでそちらで書き直した.

計算量は O(NlogN)

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
int main() {
    int N, d;
    cin >> N >> d;
    vector<tuple<int, ll, ll>> v(N);
    for(int i=0; i<N; ++i) {
        int b;
        ll x, y;
        cin >> x >> y >> b;
        v[i] = make_tuple(b, x, y);
    }
    sort(v.begin(), v.end());
 
    ll res = 0;
    multiset<ll> x, y;
    int r = 0;
    for(int l=0; l<N; ++l) {
        while(r < N && get<0>(v[r]) - get<0>(v[l]) <= d) {
            x.insert(get<1>(v[r]));
            y.insert(get<2>(v[r]));
            r++;
        }
        res = max(res, (*x.rbegin() - *x.begin()) * (*y.rbegin() - *y.begin()));
 
        if(r == N) {
            break;
        }
        x.erase(x.find(get<1>(v[l])));
        y.erase(y.find(get<2>(v[l])));
    }
    cout << res << endl;
}