Submission #1008386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008386		pudelos	Global Warming (CEOI18_glo)	C++17	100 / 100	353 ms	29968 KiB

glo

#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';
}

• 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