Submission #757811

#	Time	Username	Problem	Language	Result	Execution time	Memory
757811		taher	Global Warming (CEOI18_glo)	C++17	100 / 100	118 ms	6208 KiB

glo

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

vector<int> dp, new_dp;
 
void init(int n) {
  dp.resize(n, 1);
  new_dp.resize(n, 1);
  return ;
}
 
int fill_dp(vector<int> v) {
  int n = (int)v.size();
  if (n == 0) return 0;
  vector<int> lis;
  for(int i = 0 ; i < n ; i++) {
    int val = v[i];
    auto q = lower_bound(lis.begin(),lis.end(), val);
    int id = q - lis.begin();
    if (q == lis.end()) {
      lis.emplace_back(val);
    }
    else{
      *q = val;
    }
    dp[i] = id + 1;
  }
  return (int) lis.size();
}

void fill_new_dp(vector<int> v) {
  int n = (int)v.size();
  if (n == 0) return ;
  deque<int> lis;
  for(int i = n - 1 ; i >= 0 ; i--) {
    int val = v[i];
    auto q = lower_bound(lis.begin(),lis.end(),val, greater<int>());
    int id = q - lis.begin();
    if (q == lis.end()) {
      lis.emplace_back(val);
    }
    else *q = val;
    new_dp[i] = id + 1;
  }
  return ;
}
 
template <typename T>
class fenwick {
  public:
  vector<T> fenw;
  int n;

  fenwick(int _n) : n(_n) {
    fenw.resize(n);
  }

  void modify(int x, T v) {
    while (x < n) {
      fenw[x] = max(fenw[x], v);
      x |= (x + 1);
    }
  }

  T get(int x) {
    T v{};
    while (x >= 0) {
      v = max(v, fenw[x]);
      x = (x & (x + 1)) - 1;
    }
    return v;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, x;
  cin >> n >> x;
  init(n);
  vector<int> v(n);
  for(int i = 0 ; i < n ; i++) {
    cin >> v[i];
  }
  int here = fill_dp(v);
  fill_new_dp(v);
  if (x == 0) {
    cout << here << '\n';
    return 0;
  }
  vector<int> now_t = v;
  sort(now_t.begin(), now_t.end());
  fenwick<int> fen(n);
  int best = 0;
  for(int i = n - 1 ; i >= 0 ; i--) {
    int val = v[i];
    int idx = lower_bound(now_t.begin(),now_t.end(), val) - now_t.begin();
    int id = upper_bound(now_t.begin(),now_t.end(), val - x) - now_t.begin();
    if (id == n) {
      best = max(best, dp[i]);
      continue;
    }
    int Max = fen.get(n - id - 1);
    fen.modify(n - idx -1, new_dp[i]);
    best = max(Max + dp[i], best);
  }
  cout << best << '\n';
  return 0; 
}

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