Submission #1083450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083450		juicy	Global Warming (CEOI18_glo)	C++17	100 / 100	89 ms	5636 KiB

glo

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5;

int n, x;
int a[N], ft[2][N];

int qry(int i, int *s) {
  int res = 0;
  for (; i; i -= i & -i) {
    res = max(res, s[i]);
  }
  return res;
}

void upd(int i, int x, int *s) {
  for (; i < N; i += i & -i) {
    s[i] = max(s[i], x);
  }
} 

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> x;
  vector<int> comp;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    comp.push_back(a[i]);
  }
  sort(comp.begin(), comp.end());
  comp.erase(unique(comp.begin(), comp.end()), comp.end());
  auto id = [&](int x) {
    return lower_bound(comp.begin(), comp.end(), x) - comp.begin() + 1;
  };
  int res = 0;
  for (int i = 1; i <= n; ++i) {
    array<int, 2> dp{};
    int p = id(a[i]);
    dp[0] = qry(p - 1, ft[0]) + 1;
    dp[1] = max(qry(p - 1, ft[1]), qry(id(a[i] + x) - 1, ft[0])) + 1;
    upd(p, dp[0], ft[0]);
    upd(p, dp[1], ft[1]);
    res = max(res, dp[1]);
  } 
  cout << res;
  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