Submission #483355

#	Time	Username	Problem	Language	Result	Execution time	Memory
483355		BERNARB01	Global Warming (CEOI18_glo)	C++17	62 / 100	494 ms	38592 KiB

glo

#include <bits/stdc++.h>

using namespace std;

template<typename T = int>
struct Max {
  T val;
  const T nut = 0;
  Max() {
    val = nut;
  }
  Max(const T& _val) {
    val = _val;
  }
  void operator =(const Max& o) {
    val = o.val;
  }
  Max operator +(const Max& o) const {
    return val > o.val ? *this : o;
  }
};

template<typename T, typename T2 = int>
struct segtree {
  int b;
  vector<T> tr;
  segtree() {}
  segtree(int n) {
    b = 1;
    while (b < n) {
      b <<= 1;
    }
    tr.assign(b << 1, T());
  }
  segtree(const vector<T2>& arr) {
    b = 1;
    while (b < (int) arr.size()) {
      b <<= 1;
    }
    tr.assign(b << 1, T());
    for (int i = 0; i < (int) arr.size(); i++) {
      tr[i + b] = T(arr[i]);
    }
    bld();
  }
  void bld() {
    for (int i = b - 1; i > 0; i--) {
      tr[i] = tr[i << 1] + tr[i << 1 | 1];
    }
  }
  void upd(int i, const T2& val, bool add = false) {
    i += b;
    tr[i] = (add ? tr[i] + T(val) : T(val));
    for (i >>= 1; i > 0; i >>= 1) {
      tr[i] = tr[i << 1] + tr[i << 1 | 1];
    }
  }
  T qry(int l, int r) {
    T ansl = T(), ansr = T();
    for (l += b, r += b; l <= r; l >>= 1, r >>= 1) {
      if (l & 1) ansl = ansl + tr[l++];
      if (!(r & 1)) ansr = tr[r--] + ansr;
    }
    return ansl + ansr;
  }
  int idx_of_last_max() {
    int ret = 0;
    for (int i = 2; i < 2 * b; i <<= 1) {
      i += (tr[i + 1].val == tr[1].val);
      ret = i - b;
    }
    return ret;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, x;
  cin >> n >> x;
  vector<int> a(n);
  map<int, int> mp;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    mp[a[i]] = 0;
    mp[a[i] - x] = 0;
  }
  int id = 0;
  for (auto& [f, s] : mp) {
    s = id++;
  }
  vector<int> b(n);
  for (int i = 0; i < n; i++) {
    b[i] = mp[a[i]];
  }
  segtree<Max<>> st(id);
  int lds_len = 1;
  vector<pair<int, int>> suf(n);
  for (int i = n - 1; i >= 0; i--) {
    int j = st.qry(b[i] + 1, id).val;
    st.upd(b[i], j + 1);
    lds_len = max(lds_len, j + 1);
    suf[i] = {lds_len, st.idx_of_last_max()};
  }
  for (int i = 0; i < n; i++) {
    b[i] = mp[a[i] - x];
  }
  segtree<Max<>> stt(id);
  int ans = lds_len;
  for (int i = 0; i < n - 1; i++) {
    stt.upd(b[i], 1 + stt.qry(0, b[i] - 1).val);
    auto [sl, ns] = suf[i + 1];
    ans = max(ans, stt.qry(0, ns - 1).val + sl);
  }
  cout << ans << '\n';
  return 0;
}

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