Submission #490430

#	Time	Username	Problem	Language	Result	Execution time	Memory
490430		fun_day	Global Warming (CEOI18_glo)	C++14	0 / 100	2064 ms	9960 KiB

glo

#include <bits/stdc++.h>
 
using namespace std;

#define int long long

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;
}

// 5 8 9 12 1 2 3 14 19 20 21 15 16 17 18

int get_down_right(vector<int> v , vector<int> q , vector<int> now_t , int l , int r , int x){
  int Max = q[now_t[(int)now_t.size()-1]];
  int diff = Max - (v[r] - 1);
  int left = 0 , right = (int)now_t.size() - 1;
  int best_id = (int)now_t.size();
  if(diff > x) return 0;
  while(left <= right){
    int mid = left + (right - left) / 2;
    int val = q[now_t[mid]] - diff;
    if(val > v[l]){
     best_id = min(best_id , mid);
     right = mid - 1; 
    }
    else left = mid + 1;
  }
  return (int)now_t.size() - best_id;
}

int get_up_right(vector<int> v , vector<int> q , vector<int> now_t , int l , int r , int x){
  int Max = q[now_t[(int)now_t.size()-1]];
  int diff = v[r] - Max - 1;
  if(diff > x) return 0;
  int left = 0 , right = (int)now_t.size() - 1;
  int best_id = (int)now_t.size();
  while(left <= right){
    int mid = left + (right - left) / 2;
    int val = q[now_t[mid]] + diff;
    if(val > v[l]){
      best_id = min(best_id , mid);
      right = mid - 1;
    }
    else left = mid + 1;
  }
  return (int)now_t.size() - best_id;
}

int get_down_left(vector<int> v , vector<int> q , vector<int> now_t , int l , int r , int x){
  int Min = q[now_t[0]];
  int diff = Min - (v[l] + 1);
  if(diff > x) return 0;
  int left = 0 , right = (int)now_t.size() - 1;
  int best_id = -1;
  while(left <= right){
    int mid = left + (right - left) / 2;
    int val = q[now_t[mid]] - diff;
    if(val < v[r]){
      best_id = max(best_id , mid);
      left = mid + 1;
    }
    else right = mid - 1;
  }
  return best_id + 1;
}

int get_up_left(vector<int> v , vector<int> q , vector<int> now_t , int l , int r , int x){
  int Min = q[now_t[0]];
  int diff = v[l] - Min + 1;
  if(abs(diff) > x) return 0;
  int left = 0 , right = (int)now_t.size() - 1;
  int best_id = -1;
  while(left <= right){
    int mid = left + (right - left) / 2;
    int val = q[now_t[mid]] + diff;
    if(val < v[r]){
      best_id = max(best_id , mid);
      left = mid + 1;      
    }
    else right = mid - 1;
  }
  return best_id + 1;
}

int deb(vector<int> v , vector<int> ans , int x){
  int f_id = ans[0];
  vector<int> q;
  for(int i = 0 ; i < f_id ; i++){
    q.emplace_back(v[i] - x);    
  }
  vector<int> Lis = get_lis(q);
  if(Lis.empty()) return 0;
  int now_t = 0;
  for(int i = 0 ; i < (int)Lis.size() ; i++){
    int cur = q[Lis[i]];
    if(cur < v[f_id]) now_t++;
    else break;
  }
  return now_t;
}

int fin(vector<int> v , vector<int> ans , int x){
  int n = (int)v.size();
  int Last_id = ans[(int)ans.size() - 1];
  vector<int> q;
  for(int i = Last_id + 1 ; i < n ; i++){
    q.emplace_back(v[i] + x);    
  }
  vector<int> Lis = get_lis(q);
  if(Lis.empty()) return 0;
  int now_t = 0;
  for(int i = 0 ; i < (int)Lis.size() ; i++){
    int cur = q[Lis[i]];
    if(cur > v[Last_id]) now_t++;
  }
  return now_t;
}

int32_t 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);
    int new_ans = 0;
    if(now_t.empty()) continue;
    int Max = q[now_t[(int)now_t.size()-1]];
    int Min = q[now_t[0]];
    if(Max <= v[r]){
      assert(Max <= v[l]);
      new_ans = max(get_up_left(v , q , now_t , l , r , x) , get_up_right(v , q , now_t , l , r , x));
    }
    else if(Min >= v[l]){
      assert(Min >= v[r]);
      new_ans = max(get_down_left(v , q , now_t , l , r , x) , get_down_right(v , q , now_t , l , r , x));  
    }
    best = max(best , (int)ans.size() + new_ans);
  }
  vector<int> here;
  for(int i = 0 ; i < (int)ans.size(); i++){
    here.emplace_back(v[ans[i]]);
  }
  best = max(best , max(deb(v , ans , x) , fin(v , ans , x)) + (int)ans.size());
  cout << best << '\n';
  return 0; 
}

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