Submission #397513

#	Time	Username	Problem	Language	Result	Execution time	Memory
397513		ollel	Global Warming (CEOI18_glo)	C++17	10 / 100	1094 ms	27928 KiB

glo

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

#define rep(i,a,b) for(int i = a; i < b; i++)
#define pb push_back

typedef vector<int> vi;
typedef long long ll;

class SegTree {
public:
  vi tr; int n;

  int l(int x) {return (x<<1);}
  int r(int x) {return (x<<1)|1;}

  int combine(int a, int b) {return max(a, b);}

  void build(int i, int L, int R, vi& arr) {
    if (L == R) tr[i] = arr[L];
    else {
      int mid = (L + R) / 2;
      build(l(i), L, mid, arr);
      build(r(i), mid + 1, R, arr);
      tr[i] = combine(tr[l(i)], tr[r(i)]);
    }
  }

  void build(vi &arr) {
    build(1, 0, n - 1, arr);
  }

  SegTree(vi &arr) {
    n = arr.size();
    tr.resize(4*n);
    this->build(arr);
  }

  int query(int i, int a, int b, int L, int R) {
    if (b < a) return 0;
    if (L > b || R < a) return 0;
    if (L >= a && R <= b) return tr[i];
    int mid = (L + R) / 2;
    return combine(
      query(l(i), a, b, L, mid),
      query(r(i), a, b, mid + 1, R));
  }

  int query(int i, int j) {
    return query(1, i, j, 0, n - 1);
  }

  void update(int i, int a, int L, int R, int v) {
    if (a < L || a > R) return;
    if (L == R) {tr[i] = v; return;}
    int mid = (L + R) / 2;
    update(l(i), a, L, mid, v);
    update(r(i), a, mid + 1, R, v);
    tr[i] = combine(tr[l(i)], tr[r(i)]);
  }

  void update(int i, int v) {
    update(1, i, 0, n - 1, v);
  }
};

int n, x;
vi arr;
vi LIS, LDS;
map<int,int> cmpr;
vi vals;


void prep(vi&arr) {
  LIS.resize(n); LDS.resize(n); vals.resize(n);

  rep(i,0,n) vals[i] = arr[i];
  rep(i,0,n) vals.pb(vals[i] - x);
  sort(vals.begin(), vals.end());
  rep(i,0,2*n) {
    if (cmpr.find(vals[i]) == cmpr.end()) cmpr.insert({vals[i], i});
  }

  vi trarr(2*n, 0);
  SegTree st(trarr);
  rep(i,0,n) {
    int V = cmpr[arr[i]];
    int ans = st.query(0, V - 1) + 1;
    LIS[i] = ans;
    if (st.query(V, V) < ans) st.update(V, ans);
  }

  SegTree std(trarr);
  for (int i = n - 1; i >= 0; i--) {
    int V = cmpr[arr[i]];
    int ans = std.query(V + 1, 2*n - 1) + 1;
    LDS[i] = ans;
    if (std.query(V, V) < ans) std.update(V, ans);
  }
}

void finish() {
  int ans = LIS[n - 1];
  // vi revcmpr(n);
  // for (auto &i : cmpr) revcmpr[i.second] = i.first;
  vi trarr(2*n, 0);
  SegTree st(trarr);
  for (int i = n - 1; i >= 0; i--) {
    int V = cmpr[arr[i]];
    auto mini = lower_bound(vals.begin(), vals.end(), arr[i] - x);
    int M = *mini;
    M = cmpr[M];

    int best = st.query(M + 1, n - 1) + LIS[i];
    ans = max(ans, best);

    st.update(V, LDS[i]);
  }
  cout << ans << endl;
}

int main()
{
  cin >> n >> x;
  arr.resize(n);
  rep(i,0,n) cin>>arr[i];

  prep(arr);
  finish();
}

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