結果
問題 | No.1950 片道きゃっちぼーる |
ユーザー |
![]() |
提出日時 | 2022-05-20 22:50:01 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 463 ms / 3,000 ms |
コード長 | 1,443 bytes |
コンパイル時間 | 3,978 ms |
コンパイル使用メモリ | 237,524 KB |
実行使用メモリ | 41,272 KB |
最終ジャッジ日時 | 2024-09-20 09:11:48 |
合計ジャッジ時間 | 11,553 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll=long long; using Graph=vector<vector<int>>; #define MAX 3000 //#define MOD 1000000007 #define MOD 998244353 #define INF 1000000000 //#define INF 1000000000000000000 int main(){ int N; cin>>N; vector<ll> X(N); vector<ll> A(N); for(int i=0;i<N;i++){ cin>>X[i]; } for(int i=0;i<N;i++){ cin>>A[i]; } vector<ll> nums; for(int i=0;i<N;i++){ nums.push_back(X[i]); nums.push_back(X[i]-A[i]); nums.push_back(X[i]+A[i]); } sort(nums.begin(),nums.end()); nums.erase(unique(nums.begin(),nums.end()),nums.end()); int n=nums.size(); Graph G(n); for(int i=0;i<N;i++){ int v=lower_bound(nums.begin(),nums.end(),X[i])-nums.begin(); int nv; nv=lower_bound(nums.begin(),nums.end(),X[i]-A[i])-nums.begin(); G[nv].push_back(v); nv=lower_bound(nums.begin(),nums.end(),X[i]+A[i])-nums.begin(); G[nv].push_back(v); } vector<int> D(n,0); for(int i=0;i<n;i++){ D[i]=i; } for(int i=n-1;i>=0;i--){ if(D[i]>i){ continue; } queue<int> q; q.push(i); while(!q.empty()){ int v=q.front(); q.pop(); for(int nv:G[v]){ if(D[nv]<i){ D[nv]=i; q.push(nv); } } } } for(int i=0;i<N;i++){ int k=lower_bound(nums.begin(),nums.end(),X[i])-nums.begin(); cout<<nums[D[k]]-X[i]<<'\n'; } }