Submission #1008386

#TimeUsernameProblemLanguageResultExecution timeMemory
1008386pudelosGlobal Warming (CEOI18_glo)C++17
100 / 100
353 ms29968 KiB
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i=a; i<=b; ++i)
#define ll long long
#define eb emplace_back
#define V vector
const int base=(1<<19);
int n, X;
V<int> A;
map<int, int> ch;

struct SegTree {
  int T[2*base];
  void update(int v, int x) {
    v+=base;
    T[v]=max(T[v], x);
    v/=2;
    while(v>0) {
      T[v]=max(T[2*v], T[2*v+1]);
      v/=2;
    }
  }
  int query(int a, int b) {
    int res=0;
    a+=base-1;
    b+=base+1;
    while(a/2!=b/2) {
      if(a%2==0) res=max(res, T[a+1]);
      if(b%2==1) res=max(res, T[b-1]);
      a/=2; b/=2;
    }
    return res;
  }
} AT, BT;

signed main() {
  cin.tie(0) -> ios_base::sync_with_stdio(0);
  cin >> n >> X;
  A.resize(n+1);
  V<int> all;
  FOR(i, 1, n) {
    cin >> A[i];
    all.eb(A[i]);
    all.eb(A[i]+X);
  }
  sort(all.begin(), all.end());
  int t=0;
  for(int u : all) {
    if(ch[u]==0) ch[u]=++t;
  }
  
  FOR(i, 1, n) {
    int x = A[i];
    int sc = ch[x];
    BT.update(sc, max(BT.query(0, sc-1)+1, AT.query(0, ch[x+X]-1)+1));
    AT.update(sc, AT.query(0, sc-1)+1);
  }
  cout << max(AT.T[1], BT.T[1]) << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...