https://products.sint.co.jp/hubfs/resource/topsic/pgb/3-3.pdf
前提知識
解説
「マンハッタン距離は45度回転」という知識が無いと永久に解けない。
知らなかった場合は運が悪かったと思おう。
ある頂点からマンハッタン距離がd以下の領域はひし形の形になるが、これは扱いにくい。
頂点を「45度回転」することで、ある頂点からマンハッタン距離がd以下の領域を正方形にすることができる。
45度回転するには頂点(x,y)を(x+y,x-y)に変換することである。
これで、問題はとある正方形に含まれる頂点の数を数える問題となった。
これは二次元累積和を用いる。
0≦x+y≦6000
-3000≦x-y≦3000
なので、x-yは+3000して、非負にしておこう。
2軸とも0～6000なので、二次元累積和をするときは、6001×6001個分の領域が必要。
long longで取るとMLEするので、intで取ろう。
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<b;i++) #define rrep(i,a,b) for(int i=a;i>=b;i--) #define fore(i,a) for(auto &i:a) #define all(x) (x).begin(),(x).end() //#pragma GCC optimize ("-O3") using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); } typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60; template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; } template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; } //--------------------------------------------------------------------------------------------------- template<int VW, int VH> struct Ruisekiwa2D { int v[VH][VW]; Ruisekiwa2D() { rep(y, 0, VH) rep(x, 0, VW) v[y][x] = 0; } void set(int x, int y, int c) { v[y][x] = c; } void build() { rep(y, 0, VH) rep(x, 0, VW) { if (0 < y) v[y][x] += v[y - 1][x]; if (0 < x) v[y][x] += v[y][x - 1]; if (0 < y && 0 < x) v[y][x] -= v[y - 1][x - 1]; } } int get(int sx, int sy, int tx, int ty) { // [sx,sy]～[tx,ty] assert(sx <= tx && sy <= ty); if (sx < 0) sx = 0; if (sy < 0) sy = 0; if (VH <= ty) ty = VH - 1; if (VW <= tx) tx = VW - 1; int rs = v[ty][tx]; if (0 < sx) rs -= v[ty][sx - 1]; if (0 < sy) rs -= v[sy - 1][tx]; if (0 < sx && 0 < sy) rs += v[sy - 1][sx - 1]; return rs; } }; /*--------------------------------------------------------------------------------------------------- ∧＿∧ ∧＿∧ （´<_｀ ） Welcome to My Coding Space! （ ´_ゝ`） / ⌒i @hamayanhamayan ／ ＼ | | / /￣￣￣￣/ | ＿_(__ﾆつ/ ＿/ .| .|＿＿＿＿ ＼/＿＿＿＿/ （u ⊃ ---------------------------------------------------------------------------------------------------*/ int N, X[301010], Y[301010], D[301010]; Ruisekiwa2D<6010, 6010> r2d; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N) cin >> X[i] >> Y[i] >> D[i]; rep(i, 0, N) { int x = X[i] + Y[i]; int y = 3000 + X[i] - Y[i]; X[i] = x; Y[i] = y; r2d.set(X[i], Y[i], 1); } r2d.build(); rep(i, 0, N) { int ans = r2d.get(X[i] - D[i], Y[i] - D[i], X[i] + D[i], Y[i] + D[i]); printf("%d\n", ans); } }
