oj.uz

Submission #490281

# Submission time Handle Problem Language Result Execution time Memory
490281 2021-11-26T18:30:48 Z fun_day Global Warming (CEOI18_glo) C++14
15 / 100
 40 ms 5788 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 308 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 308 KB Output is correct
12 Incorrect 0 ms 204 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 308 KB Output is correct
12 Incorrect 0 ms 204 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 5384 KB Output is correct
2 Correct 40 ms 5324 KB Output is correct
3 Correct 37 ms 5320 KB Output is correct
4 Correct 37 ms 5316 KB Output is correct
5 Correct 33 ms 5788 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1532 KB Output is correct
2 Correct 10 ms 1528 KB Output is correct
3 Correct 10 ms 1596 KB Output is correct
4 Correct 9 ms 1612 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 9 ms 1612 KB Output is correct
7 Incorrect 9 ms 1484 KB Output isn't correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 2864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 308 KB Output is correct
12 Incorrect 0 ms 204 KB Output isn't correct
13 Halted 0 ms 0 KB -