結果
問題 | No.2248 max(C)-min(C) |
ユーザー |
|
提出日時 | 2023-03-17 23:06:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 405 ms / 3,000 ms |
コード長 | 2,071 bytes |
コンパイル時間 | 1,879 ms |
コンパイル使用メモリ | 202,224 KB |
最終ジャッジ日時 | 2025-02-11 14:15:12 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define int long long#define INF (int)1e18#define f first#define s secondmt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());const int N = 2e5 + 69;int a[N], b[N], c[N];int seg[4*N];int n;void Build(int l, int r, int pos){if (l==r) {seg[pos] = a[l];return;}int mid = (l+r)/2;Build(l, mid, pos*2);Build(mid + 1, r, pos*2 + 1);seg[pos] = max(seg[pos * 2], seg[pos * 2 + 1]);}void Update(int l, int r, int pos, int qp){if (l==r){seg[pos] = min(a[l], min(b[l], c[l]));return;}int mid = (l+r)/2;if (qp <= mid) Update(l, mid, pos*2, qp);else Update(mid + 1, r, pos*2 + 1, qp);seg[pos] = max(seg[pos * 2], seg[pos * 2 + 1]);}void Solve(){cin>>n;for (int i=1; i<=n; i++)cin>>a[i];for (int i=1; i<=n; i++){cin>>c[i];if (a[i] > c[i]) swap(a[i], c[i]);b[i] = (a[i] + c[i])/2;}Build(1, n, 1);vector <pair<int, pair<int, int>>> v;for (int i=1; i<=n; i++){v.push_back({a[i], {i, 1}});v.push_back({b[i], {i, 2}});v.push_back({c[i], {i, 3}});}sort(v.begin(), v.end());int ans = INF;for (auto x: v){ans = min(seg[1] - x.f, ans);if (x.s.s == 1){a[x.s.f] = INF;} else if (x.s.s == 2){b[x.s.f] = INF;} else c[x.s.f] = INF;Update(1, n, 1, x.s.f);}cout<<ans<<"\n";}int32_t main(){auto begin = std::chrono::high_resolution_clock::now();ios_base::sync_with_stdio(0);cin.tie(0);int t = 1;// cin >> t;for(int i = 1; i <= t; i++){//cout << "Case #" << i << ": ";Solve();}auto end = std::chrono::high_resolution_clock::now();auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";return 0;}