fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. const ll INF = 2e18;
  7. const int N = 1e6 + 5;
  8.  
  9. int n;
  10. ll a[N], b[N];
  11. int id[N], d[N];
  12.  
  13. void add(int l, int r) {
  14.     if (l > r) {
  15.         add(0, r);
  16.         add(l, n - 1);
  17.         return;
  18.     }
  19.     d[l]++;
  20.     d[r + 1]--;
  21. }
  22.  
  23. bool ok(ll lim) {
  24.     fill(d, d + n, 0);
  25.     int pos = n;
  26.     for (int i = 0; i < n; i++) {
  27.         while (pos > 0 && a[id[i]] + b[pos - 1] >= lim) pos--;
  28.         if (pos == n) return 0;
  29.         int l = id[i] - (n - 1), r = id[i] - pos;
  30.         if (l < 0) l += n;
  31.         if (r < 0) r += n;
  32.         add(l, r);
  33.     }
  34.     for (int i = 0; i < n; i++) {
  35.         if (d[i] == n) return 1;
  36.         d[i + 1] += d[i];
  37.     }
  38.     return 0;
  39. }
  40.  
  41. int main() {
  42.     ios::sync_with_stdio(false), cin.tie(0);
  43.     cin >> n;
  44.     for (int i = 0; i < n; i++) cin >> a[i];
  45.     for (int i = 0; i < n; i++) cin >> b[i];
  46.  
  47.     iota(id, id + n, 0);
  48.     sort(id, id + n, [&](int l, int r) {
  49.         return a[l] < a[r];
  50.     });
  51.  
  52.     ll l = 0, r = INF;
  53.     while (l < r) {
  54.         ll mid = (l + r) / 2 + 1;
  55.         if (ok(mid)) l = mid;
  56.         else r = mid - 1;
  57.     }
  58.     cout << l << '\n';
  59. }
Success #stdin #stdout 0.01s 5532KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/vWES7T
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!