fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define cint const int
  5. #define left(id) (id << 1)
  6. #define right(id) (id << 1 | 1)
  7.  
  8. const int MAXN = 2e5 + 15;
  9. const int oo   = 1e18;
  10.  
  11. int N, K;
  12. int A[MAXN];
  13.  
  14. struct Seg {
  15.     int it[MAXN * 4];
  16.     void update(cint &id, cint &l, cint &r, cint &u, cint &v, cint &val) {
  17.         if (l > v || r < u) return;
  18.         if (u <= l && r <= v) return void(it[id] = min(it[id], val));
  19.  
  20.         int mid = (l + r) / 2;
  21.         update(left(id), l, mid, u, v, val);
  22.         update(right(id), mid + 1, r, u, v, val);
  23.  
  24.         it[id] = min(it[left(id)], it[right(id)]);
  25.     }
  26.  
  27.     int get(cint &id, cint &l, cint &r, cint &u, cint &v) {
  28.         if (l > v || r < u) return oo;
  29.         if (u <= l && r <= v) return it[id];
  30.  
  31.         int mid = (l + r) / 2;
  32.         int it1 = get(left(id), l, mid, u, v);
  33.         int it2 = get(right(id), mid + 1, r, u, v);
  34.  
  35.         return min(it1, it2);
  36.     }
  37.  
  38.     int walk(cint &id, cint &l, cint &r, cint &u, cint &v, cint &val) {
  39.         if (l > v || r < u || it[id] > val) return -1;
  40.         if (l == r) return l;
  41.  
  42.         int mid = (l + r) / 2;
  43.         int it2 = walk(right(id), mid + 1, r, u, v, val);
  44.         if (it2 == -1) return walk(left(id), l, mid, u, v, val);
  45.         else return it2;
  46.     }
  47.  
  48.     void INIT() {
  49.         memset(it, 60, sizeof it);
  50.         update(1, 0, N, 0, 0, -oo);
  51.     }
  52. } ST;
  53.  
  54. bool check(int G) {
  55.     int best = 0;
  56.     ST.INIT();
  57.     for (int i = 1; i <= N; i++) {
  58.         if (A[i] == -1) {
  59.             int a = ST.get(1, 0, N, best, best) + G;
  60.             if (best == 0) a = -oo;
  61.             ST.update(1, 0, N, best + 1, best + 1, a);
  62.             best++;
  63.             if (best >= K) return true;
  64.             continue;
  65.         }
  66.         int nr = ST.walk(1, 0, N, 0, best, A[i] - G);
  67.         ST.update(1, 0, N, nr + 1, nr + 1, A[i]);
  68.         best = max(best, nr + 1);
  69.         if (best >= K) return true;
  70.     }
  71.     return 0;
  72. }
  73.  
  74.  
  75. signed main() {
  76.     ios_base::sync_with_stdio(0);
  77.     cin.tie(0);
  78.     cout.tie(0);
  79.  
  80.     cin >> N >> K;
  81.     for (int i = 1; i <= N; i++) cin >> A[i];
  82.  
  83.     int l = -1, r = oo;
  84.     while (r > l + 1) {
  85.         int mid = (l + r) / 2;
  86.         if (check(mid)) l = mid;
  87.         else r = mid;
  88.     }
  89.     if (check(oo)) cout << "Infinity";
  90.     else cout << l;
  91.  
  92. }
  93.  
Success #stdin #stdout 0.02s 9960KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/3lMPUx
language:
C++14 (gcc 8.3)
created:
2 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!