Submission #1196880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196880		LucaLucaM	Global Warming (CEOI18_glo)	C++20	100 / 100	297 ms	9108 KiB

glo

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <map>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

const int NMAX = 2e5;
const int INF = 1e9;

int a[NMAX + 1];
int prefLis[NMAX + 1];
int suffLis[NMAX + 1];

struct Fenwick {
  int n;
  std::vector<int> aib;
  
  Fenwick() {}
  
  void init(int _n) {
    n = _n + 1;
    aib.resize(n + 1);
    aib.assign(n + 1, 0);
  }
  void update(int pos, int value) {
    for (; pos <= n; pos += pos & -pos) {
      aib[pos] = std::max(aib[pos], value);
    }
  }
  int query(int pos) {
    int ret = 0;
    for (; pos > 0; pos -= pos & -pos) {
      ret = std::max(ret, aib[pos]);
    }
    return ret;
  }
};

int main() {
  #ifdef LOCAL
    freopen("input.txt", "r", stdin);
  #endif
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  int n, X; 
  std::cin >> n >> X;

  std::vector<int> norm;

  for (int i = 1; i <= n; i++) {
    std::cin >> a[i];
    norm.push_back(a[i]);
    norm.push_back(-a[i]);
    norm.push_back(X + a[i] - 1);
    norm.push_back(-(a[i] - X + 1));
  }

  std::sort(norm.begin(), norm.end());
  norm.erase(std::unique(norm.begin(), norm.end()), norm.end());

  auto get = [&](int x) {
    return std::lower_bound(norm.begin(), norm.end(), x) - norm.begin() + 1;
  };
  
  Fenwick aib;
  aib.init((int) norm.size() + 1);

  for (int i = 1; i <= n; i++) {
    prefLis[i] = 1 + aib.query(get(a[i]) - 1);
    aib.update(get(a[i]), prefLis[i]);
  }

  aib.init((int) norm.size() + 1);
  for (int i = n; i > 0; i--) {
    suffLis[i] = 1 + aib.query(get(-a[i]) - 1);
    aib.update(get(-a[i]), suffLis[i]);
  }

  aib.init((int) norm.size() + 1);

  int answer = 0;
  for (int i = 1; i <= n; i++) {
    answer = std::max(answer, prefLis[i]);
  }

  for (int i = 1; i <= n; i++) {
    answer = std::max(answer, suffLis[i] + aib.query(get(X + a[i] - 1)));
    aib.update(get(a[i]), prefLis[i]);
  }

  aib.init((int) norm.size() + 1);
  
  for (int i = n; i > 0; i--) {
    // -a[j] <= -(a[i] - X + 1)
    answer = std::max(answer, prefLis[i] + aib.query(get(-(a[i] - X + 1))));
    aib.update(get(-a[i]), suffLis[i]);
  }
  
  std::cout << answer;
  
  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