提出 #4545495


ソースコード 拡げる

Copy
#include<bits/stdc++.h>

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;
const int inf = (1 << 30) - 1;
const int64 infll = (1LL << 61) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}

vector< int > Luzhiled(vector< int > &X, vector< int > &Y, int D) {
  int N = (int) X.size();
  map< int, vector< pair< int, int > > > XX, YY;
  vector< int > ans(N);
  for(int i = 0; i < N; i++) {
    XX[X[i]].emplace_back(Y[i], i);
    YY[Y[i]].emplace_back(X[i], i);
  }
  for(auto &v : XX) sort(begin(v.second), end(v.second));
  for(auto &v : YY) sort(begin(v.second), end(v.second));
  for(int i = 0; i < N; i++) {
    for(auto x : {X[i] - D, X[i] + D}) {
      if(XX.count(x)) {
        auto o = XX[x];
        ans[i] += lower_bound(begin(o), end(o), make_pair(Y[i] + D, -1)) -
                  lower_bound(begin(o), end(o), make_pair(Y[i] - D, inf));
      }
    }
    for(auto y : {Y[i] - D, Y[i] + D}) {
      if(YY.count(y)) {
        auto o = YY[y];
        ans[i] += lower_bound(begin(o), end(o), make_pair(X[i] + D, inf)) -
                  lower_bound(begin(o), end(o), make_pair(X[i] - D, -inf));
      }
    }
  }
  return ans;
}

int main() {
  int N, A, B;
  cin >> N >> A >> B;
  --A, --B;
  vector< int > X(N), Y(N);


  map< int, map< int, int > > XX, YY;

  for(int i = 0; i < N; i++) {
    int a, b;
    cin >> a >> b;
    X[i] = a - b;
    Y[i] = a + b;
    XX[X[i]][Y[i]] = i;
    YY[Y[i]][X[i]] = i;
  }


  int D = max(abs(X[A] - X[B]), abs(Y[A] - Y[B]));

  vector< int > v(N);
  queue< int > que;
  v[A] = true;
  v[B] = true;
  que.emplace(A);
  que.emplace(B);


  while(que.size()) {
    auto p = que.front();
    que.pop();
    for(auto x : {X[p] - D, X[p] + D}) {
      if(XX.count(x)) {
        auto &o = XX[x];
        auto L = o.lower_bound(Y[p] - D);
        auto R = o.upper_bound(Y[p] + D);
        while(L != R) {
          if(!v[L->second]) {
            v[L->second] = true;
            que.emplace(L->second);
          }
          L = o.erase(L);
        }
      }
    }

    for(auto y : {Y[p] - D, Y[p] + D}) {
      if(YY.count(y)) {
        auto &o = YY[y];
        auto L = o.lower_bound(X[p] - D);
        auto R = o.upper_bound(X[p] + D);
        while(L != R) {
          if(!v[L->second]) {
            v[L->second] = true;
            que.emplace(L->second);
          }
          L = o.erase(L);
        }
      }
    }
  }
  auto tap = Luzhiled(X, Y, D);
  int64 ret = 0;
  for(int i = 0; i < N; i++) ret += 1LL * tap[i] * v[i];
  cout << ret / 2 << endl;
}


提出情報

提出日時
問題 E - へんなコンパス
ユーザ ei13333
言語 C++14 (GCC 5.4.1)
得点 0
コード長 3859 Byte
結果
実行時間 3160 ms
メモリ 41600 KB

ジャッジ結果

セット名 得点 / 配点 テストケース
Sample 0 / 0 subtask0_0.txt, subtask0_1.txt, subtask0_2.txt
All 0 / 900 subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_2.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt
ケース名 結果 実行時間 メモリ
subtask0_0.txt 2 ms 256 KB
subtask0_1.txt 2 ms 256 KB
subtask0_2.txt 1 ms 256 KB
subtask1_0.txt 3157 ms 28888 KB
subtask1_1.txt 3157 ms 28756 KB
subtask1_10.txt 563 ms 26112 KB
subtask1_11.txt 222 ms 13952 KB
subtask1_12.txt 208 ms 31992 KB
subtask1_13.txt 212 ms 32120 KB
subtask1_14.txt 636 ms 40320 KB
subtask1_15.txt 219 ms 13952 KB
subtask1_16.txt 3156 ms 31460 KB
subtask1_17.txt 3160 ms 31076 KB
subtask1_18.txt 316 ms 11008 KB
subtask1_19.txt 221 ms 13952 KB
subtask1_2.txt 494 ms 41600 KB
subtask1_20.txt 3157 ms 29304 KB
subtask1_21.txt 3157 ms 29304 KB
subtask1_22.txt 305 ms 11008 KB
subtask1_23.txt 295 ms 11392 KB
subtask1_24.txt 3157 ms 29416 KB
subtask1_3.txt 285 ms 13568 KB
subtask1_4.txt 3157 ms 29048 KB
subtask1_5.txt 3157 ms 29048 KB
subtask1_6.txt 316 ms 11648 KB
subtask1_7.txt 278 ms 13568 KB
subtask1_8.txt 246 ms 31608 KB
subtask1_9.txt 3157 ms 28792 KB