Advertisement
YEZAELP

o60_may05_teamassignment

Jan 31st, 2022
726
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const bool Debug = false;
  5. const int inf = 1e9;
  6. const int N = 1e5 + 10;
  7. vector <int> coor;
  8. int ar[N];
  9. int n, mnc, mxc;
  10.  
  11. /// ก่อน optimization
  12. /*
  13. bool Check(int limit){
  14.     bool dp[n + 5] = {false};
  15.     dp[n + 1] = true;
  16.     for(int i = n; i >= 1; i --){
  17.         int mx = -inf;
  18.         for(int j = i; j <= i + mnc - 2; j ++)
  19.             mx = max(mx, ar[j]);
  20.         for(int j = i + mnc - 1; j <= min(n, i + mxc - 1); j ++){
  21.             mx = max(mx, ar[j]);
  22.             if(mx >= limit) dp[i] = dp[i] | dp[j + 1];
  23.         }
  24.     }
  25.     return dp[1];
  26. }
  27. */
  28.  
  29. bool Check(int limit){
  30.     bool dp[n + 5] = {false};
  31.     deque <int> pst;
  32.     vector <int> Tdp;
  33.     dp[0] = 1, Tdp.push_back(0);
  34.     int sz = 1;
  35.  
  36.     for(int i = 1; i <= mnc - 1; i ++) if(ar[i] >= limit) pst.push_back(i);
  37.  
  38.     for(int i = mnc; i <= n; i ++){
  39.         while(!pst.empty() and i - pst.front() + 1 > mxc) pst.pop_front();
  40.         if(ar[i] >= limit) pst.push_back(i);
  41.         if(pst.empty()) continue;
  42.  
  43.         int s = max(0, i - mxc + 1 - 1), e = min(i - mnc + 1 - 1, pst.back() - 1), l, r, mn = inf, mx = -inf;
  44.  
  45.         /// s <= mn
  46.         l = 0, r = sz - 1;
  47.         while(l <= r){
  48.             int mid = (l + r) / 2;
  49.             if(s <= Tdp[mid]) r = mid - 1, mn = min(mn, mid);
  50.             else l = mid + 1;
  51.         }
  52.         /// s <= mx
  53.         l = 0, r = sz - 1;
  54.         while(l <= r){
  55.             int mid = (l + r) / 2;
  56.             if(Tdp[mid] <= e) l = mid + 1, mx = max(mx, mid);
  57.             else r = mid - 1;
  58.         }
  59.         if(mn <= mx) dp[i] = true, Tdp.push_back(i), sz ++;
  60.     }
  61.  
  62.     return dp[n];
  63. }
  64.  
  65. int main(){
  66.  
  67.     scanf("%d %d %d", &n, &mnc, &mxc);
  68.  
  69.     for(int i = 1; i <= n; i ++)
  70.         scanf("%d", &ar[i]),
  71.         coor.push_back(ar[i]);
  72.  
  73.     sort(coor.begin(), coor.end());
  74.     coor.resize( unique(coor.begin(), coor.end()) - coor.begin() );
  75.  
  76.     int idx = -1, l = 0, r = coor.size() - 1;
  77.     while(l <= r){
  78.         int mid = (l + r) / 2;
  79.         bool ch = Check(coor[mid]);
  80.         if(ch)
  81.             l = mid + 1,
  82.             idx = max(idx, mid);
  83.         else
  84.             r = mid - 1;
  85.     }
  86.  
  87.     printf("%d", idx == -1 ? idx: coor[idx]);
  88.  
  89.     return 0;
  90. }
  91.  
  92. /// Test Case
  93. /*
  94.  
  95. 10 3 4
  96. 10 20 15 18 1 2 1 2 4 30
  97.  
  98. 10 6 7
  99. 10 20 15 18 1 2 1 2 4 30
  100.  
  101. 10 3 10
  102. 2 1 4 19 2 34 3 2 4 5
  103. 34
  104.  
  105. */
Advertisement
RAW Paste Data Copied
Advertisement