結果
問題 | No.2248 max(C)-min(C) |
ユーザー |
![]() |
提出日時 | 2023-03-17 21:46:14 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 481 ms / 3,000 ms |
コード長 | 1,330 bytes |
コンパイル時間 | 902 ms |
コンパイル使用メモリ | 73,648 KB |
実行使用メモリ | 30,788 KB |
最終ジャッジ日時 | 2024-09-18 10:35:33 |
合計ジャッジ時間 | 11,558 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 |
ソースコード
#include <stdio.h>#include <vector>#include <algorithm>#include <map>#include <set>#define MAX (int)2e9 + 1int x[200010],y[200010];std::vector<int> index;std::map<int,int> hash;std::set< std::pair<int,int> > S;std::vector<int> V[200010];int main(){int a;scanf("%d",&a);for(int i=1;i<=a;i++) scanf("%d",&x[i]);for(int i=1;i<=a;i++) scanf("%d",&y[i]);for(int i=1;i<=a;i++){V[i].push_back(x[i]);V[i].push_back(y[i]);V[i].push_back((x[i]+y[i])/2);V[i].push_back(MAX);std::sort(V[i].begin(),V[i].end());std::reverse(V[i].begin(),V[i].end());S.insert(std::make_pair(V[i].back(),i));}for(int i=1;i<=a;i++) for(int j=0;j<V[i].size();j++) index.push_back(V[i][j]);std::sort(index.begin(),index.end());index.erase(std::unique(index.begin(),index.end()),index.end());int ans = MAX;for(int i=0;i<index.size();i++){int limit = index[i];while(!S.empty()){std::set< std::pair<int,int> > ::iterator it = S.begin();int val = (it->first), ind = (it->second);if(val<limit){S.erase(it);V[ind].pop_back();S.insert(std::make_pair(V[ind].back(),ind));}else break;}std::set< std::pair<int,int> > ::iterator it = S.end();it--;int val = (it->first);if(val>=MAX) break;ans = ans<val-limit?ans:val-limit;}printf("%d",ans);}