結果
問題 | No.2248 max(C)-min(C) |
ユーザー |
![]() |
提出日時 | 2023-03-19 23:13:41 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 357 ms / 3,000 ms |
コード長 | 1,598 bytes |
コンパイル時間 | 5,639 ms |
コンパイル使用メモリ | 143,220 KB |
実行使用メモリ | 23,116 KB |
最終ジャッジ日時 | 2024-09-18 13:54:21 |
合計ジャッジ時間 | 13,293 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 |
ソースコード
#include <cassert>#include <cmath>#include <algorithm>#include <iostream>#include <iomanip>#include <climits>#include <map>#include <queue>#include <set>#include <cstring>#include <vector>using namespace std;typedef long long ll;struct Node {int i;int c;Node(int i = -1, int c = -1) {this->i = i;this->c = c;}bool operator>(const Node &n) const {return c > n.c;}};int main() {int N;cin >> N;vector<int> A(N);vector<int> B(N);for (int i = 0; i < N; ++i) {cin >> A[i];}for (int i = 0; i < N; ++i) {cin >> B[i];}vector<int> nums;priority_queue <Node, vector<Node>, greater<Node>> pque;int cand[N][5];for (int i = 0; i < N; ++i) {int a = A[i];int b = B[i];if (a > b) {int t = a;a = b;b = t;}cand[i][0] = INT_MIN;cand[i][1] = a;cand[i][2] = (a + b) / 2;cand[i][3] = b;cand[i][4] = INT_MAX;nums.push_back(a);nums.push_back(b);nums.push_back((a + b) / 2);pque.push(Node(i, INT_MIN));pque.push(Node(i, a));pque.push(Node(i, b));pque.push(Node(i, (a + b) / 2));pque.push(Node(i, INT_MAX));}sort(nums.begin(), nums.end());vector<int> cur_pos(N, 0);int ans = INT_MAX;int max_c = 0;for (int min_c : nums) {while (not pque.empty() && pque.top().c < min_c) {Node node = pque.top();pque.pop();cur_pos[node.i]++;max_c = max(max_c, cand[node.i][cur_pos[node.i]]);}ans = min(ans, max_c - min_c);}cout << ans << endl;return 0;}