fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5. #define ii pair<int, int>
  6. #define fi first
  7. #define se second
  8.  
  9. using namespace std;
  10.  
  11. const int maxn = 5e5;
  12. const ll INF = 1e18;
  13.  
  14. int n, k, lmax[maxn + 10], rmax[maxn + 10], lprovide[maxn + 10], rprovide[maxn + 10];
  15. ll h[maxn + 10], pre[maxn + 10];
  16. vector<int> stk;
  17. ii vl[maxn + 10];
  18.  
  19. void build_lprovide(ll x)
  20. {
  21.     int j = 1;
  22.     for (int i = 1; i <= n; i++)
  23.     {
  24.         while (pre[i - 1] - pre[j - 1] > x)
  25.             j++;
  26.         lprovide[i] = max(j, lmax[i]);
  27.     }
  28. }
  29. void build_rprovide(ll x)
  30. {
  31.     int j = n;
  32.     for (int i = n; i >= 1; i--)
  33.     {
  34.         while (pre[j - 1] - pre[i - 1] > x)
  35.             j--;
  36.         rprovide[i] = min(j, rmax[i]);
  37.     }
  38. }
  39. bool check(ll x)
  40. {
  41.     for (int i = 1; i <= n; i++)
  42.         vl[i] = {0, 0};
  43.     build_lprovide(x);
  44.     build_rprovide(x);
  45.     for (int i = 1; i <= n; i++)
  46.         vl[lprovide[i]] = max(vl[lprovide[i]], {rprovide[i], -i});
  47.     int rt = 0;
  48.     int j = 1;
  49.     ii mx = {0, n};
  50.     int cnt = 0;
  51.  
  52. //    for (int i = 1; i <= n; i++)
  53. //        cout << i << ' ' << lprovide[i] << ' ' << rprovide[i], el;
  54.  
  55.     while (rt < n)
  56.     {
  57.         ii tmp = mx;
  58.         for (; j <= rt; j++)
  59.             mx = max(mx, vl[j]);
  60. //            if (-pr.se - (rt + 1) <= (rt + 1) + tmp.se)
  61.         mx = max(mx, vl[rt + 1]);
  62. //        cout << mx.fi << ' ' << mx.se, el;
  63.         if (mx.fi == rt)
  64.             return 0;
  65.         rt = mx.fi;
  66.         cnt++;
  67.     }
  68.     return cnt <= k;
  69. }
  70. ll bs(ll l, ll r)
  71. {
  72.     ll ans = -1;
  73.     while (l <= r)
  74.     {
  75.         ll m = l + r >> 1;
  76.         if (check(m))
  77.         {
  78.             ans = m;
  79.             r = m - 1;
  80.         }
  81.         else
  82.             l = m + 1;
  83.     }
  84.     return ans;
  85. }
  86.  
  87. int main()
  88. {
  89.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  90.     if (fopen("FIRE.INP", "r"))
  91.     {
  92.         freopen("FIRE.INP", "r", stdin);
  93.         freopen("FIRE.OUT", "w", stdout);
  94.     }
  95.  
  96.     cin >> n >> k;
  97.     for (int i = 1; i <= n; i++)
  98.         cin >> h[i];
  99.     for (int i = 1; i < n; i++)
  100.     {
  101.         cin >> pre[i];
  102.         pre[i] += pre[i - 1];
  103.     }
  104.     h[0] = h[n + 1] = INF;
  105.     stk.push_back(0);
  106.     for (int i = 1; i <= n; i++)
  107.     {
  108.         while (h[stk.back()] < h[i])
  109.             stk.pop_back();
  110.         lmax[i] = max(1, stk.back());
  111.         stk.push_back(i);
  112.     }
  113.     stk.clear();
  114.     stk.push_back(n + 1);
  115.     for (int i = n; i >= 1; i--)
  116.     {
  117.         while (h[stk.back()] < h[i])
  118.             stk.pop_back();
  119.         rmax[i] = min(n, stk.back());
  120.         stk.push_back(i);
  121.     }
  122. //    cout << check(6);
  123. //    for (int i = 1; i <= 10; i++)
  124. //        cout << i << ' ' << check(i), el;
  125.     cout << bs(0, INF);
  126. }
  127.  
Success #stdin #stdout 0.01s 7724KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/Zswky6
language:
C++14 (gcc 8.3)
created:
9 days ago
visibility:
public

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!