結果

問題 No.2897 ２集合間距離
ユーザー vjudge1vjudge1
提出日時 2024-09-25 16:26:18
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,236 ms / 3,500 ms
コード長 863 bytes
コンパイル時間 2,083 ms
コンパイル使用メモリ 207,692 KB
実行使用メモリ 17,764 KB
最終ジャッジ日時 2024-09-25 16:26:35
合計ジャッジ時間 12,060 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
14,132 KB
testcase_01 AC 5 ms
13,508 KB
testcase_02 AC 6 ms
14,848 KB
testcase_03 AC 6 ms
13,420 KB
testcase_04 AC 5 ms
14,296 KB
testcase_05 AC 5 ms
14,228 KB
testcase_06 AC 5 ms
14,844 KB
testcase_07 AC 5 ms
13,876 KB
testcase_08 AC 6 ms
14,916 KB
testcase_09 AC 5 ms
14,388 KB
testcase_10 AC 4 ms
14,276 KB
testcase_11 AC 5 ms
14,452 KB
testcase_12 AC 7 ms
14,420 KB
testcase_13 AC 11 ms
13,600 KB
testcase_14 AC 15 ms
14,088 KB
testcase_15 AC 66 ms
15,040 KB
testcase_16 AC 1,214 ms
16,148 KB
testcase_17 AC 1,222 ms
16,900 KB
testcase_18 AC 1,236 ms
17,456 KB
testcase_19 AC 1,216 ms
16,460 KB
testcase_20 AC 1,225 ms
17,032 KB
testcase_21 AC 967 ms
16,804 KB
testcase_22 AC 882 ms
16,532 KB
testcase_23 AC 893 ms
17,764 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int n, y, x, a[N], now, m, sz[N], ans = 1e9, it[N];
vector<int>e[N], g[N];

int main(){
  cin >> n;
  for(int i = 1; i <= n; ++i){
    cin >> a[i] >> y;
    g[y].push_back(a[i]);
  }
  cin >> m;
  for(int i = 1; i <= m; i++){
    cin >> x >> y;
    e[x].push_back(y);
  }
  for(int i = 0; i < 1000; ++i){
    g[i].push_back(-1);
    sort(g[i].begin(), g[i].end());
    it[i] = 0;
  }
  for(int i = 0; i < 1000; ++i){
    for(auto v : e[i]){
      for(int j = 0; j < 1000; ++j){
        for(; it[j] < g[j].size() && g[j][it[j]] < i; it[j]++){
        }
        if(it[j] != g[j].size()){
          ans = min(ans, g[j][it[j]] - i + abs(v - j));
        }
        if(it[j] > 1){
          ans = min(ans, i - g[j][it[j] - 1] + abs(v - j));
        }
      }
    }
  }
  cout << ans;
  return 0;
}
0