結果

問題 No.2897 ２集合間距離
コンテスト
ユーザー vjudge1
提出日時 2024-09-25 16:26:18
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,295 ms / 3,500 ms
コード長 863 bytes
コンパイル時間 2,293 ms
コンパイル使用メモリ 199,696 KB
最終ジャッジ日時 2025-02-24 12:15:24
ジャッジサーバーID
（参考情報） 		judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

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