Submission #490281

#	Time	Username	Problem	Language	Result	Execution time	Memory
490281		fun_day	Global Warming (CEOI18_glo)	C++14	15 / 100	40 ms	5788 KiB

glo

#include <bits/stdc++.h>

using namespace std;

vector<int> get_lis(vector<int> v){
  int n = (int)v.size();
  if(n == 0) return {};
  vector<int> lis;
  vector<int> Last(n + 1 , -1) , p (n + 1 , -1);
  for(int i = 0 ; i < n ; i++){
    int val = v[i];
    auto q = lower_bound(lis.begin(),lis.end() , val);
    int idx = q - lis.begin();
    if(q == lis.end()){
      lis.emplace_back(val);
    }
    else{
      *q = val;
    }
    Last[i] = (idx > 0 ? p[idx - 1] : -1);
    p[idx] = i;
  }
  vector<int> ans;
  int sz = (int)lis.size();
  for(int i = p[sz - 1] ; i != -1 ; i = Last[i]){
    ans.emplace_back(i);
  }
  reverse(ans.begin() , ans.end());
  return ans;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n , x;
  cin >> n >> x;
  vector<int> v(n);
  for(int i = 0 ; i < n ; i++){
    cin >> v[i];
  }
  vector<int> ans = get_lis(v);
  int best = (int)ans.size();
  for(int i = 1 ; i < (int)ans.size() ; i++){
    int l = ans[i - 1];
    int r = ans[i];
    vector<int> q;
    for(int k = l + 1 ; k < r ; k++){
      q.emplace_back(v[k]);
    }
    vector<int> now_t = get_lis(q);
    if(now_t.empty()) continue;
    int a = now_t[0] , b = now_t[(int)now_t.size()-1];
    int d = abs(q[b] - v[r]) + (q[b] >= v[r] ? 1 : -1);
    if(!(d >= -x && d <= x)) continue;
    int left = 0 , right = (int)now_t.size() - 1;
    int best_id = 0;
    while(left <= right){
      int mid = left + (right - left) / 2;
      if(q[now_t[mid]] - d >= q[a]){
        best_id = mid;
        right = mid - 1;
      }
      else{
        left = mid + 1;
      }
    }
    int new_ans = (int)ans.size() + (int)now_t.size() - best_id;    
    best = max(best , new_ans);
    left = 0 , right = (int)now_t.size() - 1;
    int new_d = abs(q[a] -  v[l]) + (q[a] >= v[l] ? -1 : 1);
    int new_id = (int)now_t.size() - 1;
    if(!(new_d >= -x && new_d <= x)) continue;
    while(left <= right){
      int mid = left + (right - left) / 2;
      if(q[now_t[mid]] - new_d <= q[b]){
        new_id = mid;
        left = mid + 1;
      }
      else right = mid - 1;
    }
    best = max(best , (int)ans.size() + new_id + 1);
  }
  int r = ans[0];
  vector<int> q;
  for(int i = 0 ; i < r ; i++) {
    q.emplace_back(v[i]);
  }
  vector<int> take = get_lis(q);
  if(!take.empty()){
    int idx_last = take[(int)take.size()- 1];
    int diff = - v[r] + q[idx_last] + (q[idx_last] >= v[r] ? 1 : -1);
    if(diff >= -x && diff <= x) best = max(best , (int)ans.size() + (int)take.size());
  }
  vector<int> Last;
  for(int i = ans[(int)ans.size() - 1] + 1 ; i < n ; i++){
    Last.emplace_back(v[i]);
  }
  vector<int> get = get_lis(Last);
  if(!get.empty()){
    int j = get[0];
    int val = v[ans[(int)ans.size()-1]];
//    int new_diff = v[ans[(int)ans.size()-1]] - Last[j] + 1;
    int new_diff = abs(Last[j] -  val) + (Last[j] >= val ? -1 : 1);
    if(new_diff >= -x && new_diff <= x) best = max(best , (int)ans.size() + (int)get.size());
  }
  cout << best << '\n';
  return 0; 
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25