結果
問題 |
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 + 1 int 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); }