結果
問題 |
No.1950 片道きゃっちぼーる
|
ユーザー |
|
提出日時 | 2023-07-17 16:40:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,949 ms / 3,000 ms |
コード長 | 2,046 bytes |
コンパイル時間 | 1,420 ms |
コンパイル使用メモリ | 128,036 KB |
最終ジャッジ日時 | 2025-02-15 15:27:39 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
/* */ #include<iostream> #include<set> #include<algorithm> #include<vector> #include<string> #include<set> #include<map> #include<numeric> #include<queue> #include<cmath> #include <unordered_set> using namespace std; typedef long long ll; const ll INF=1LL<<60; typedef pair<ll,ll> P; typedef pair<int,P> PP; const ll MOD=1e9+7; 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> d; for(int i=0;i<N;i++){ //mp[X[i]]=i;//X[i]に人iがいる d.push_back(X[i]); d.push_back(X[i]+A[i]); d.push_back(X[i]-A[i]); } set<ll> setd(d.begin(),d.end()); map<ll,ll> mpd; int sz=0; for(ll val:setd){ mpd[val]=sz; sz++; } map<ll,ll> rev; for(auto [val,idx]:mpd){ rev[idx]=val; } vector<vector<int>> G(sz),rG(sz); set<pair<int,int>> edges; for(int i=0;i<N;i++){ //k番目から辺を張る int k=mpd[X[i]]; { int j=mpd[X[i]+A[i]]; G[j].push_back(k); rG[k].push_back(j); } { int j=mpd[X[i]-A[i]]; G[j].push_back(k); rG[k].push_back(j); } } vector<bool> vis(sz,false); vector<ll> ans(sz); for(int i=0;i<sz;i++){ ans[i]=rev[i];//i番目のポジション. } auto dfs=[&](auto f,int now)->void{ vis[now]=true; for(int to:G[now]){ if(vis[to]) continue; ans[to]=max(ans[to],ans[now]); f(f,to); } }; //インデックスが大きいほどx方向への正の方向への絶対値がおおきい // for(int i=sz-1;i>=0;i--){ if(!vis[i]){ dfs(dfs,i); } } for(int i=0;i<N;i++){ cout<<ans[mpd[X[i]]]-X[i]<<endl; } }