Submission #1008379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008379		pudelos	Global Warming (CEOI18_glo)	C++17	27 / 100	504 ms	38340 KiB

glo

#include <bits/stdc++.h>
using namespace std;
#define int long long
#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<<20);
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];
    AT.update(ch[x], AT.query(0, ch[x]-1)+1);
    BT.update(ch[x], BT.query(0, ch[x]-1)+1);
    BT.update(ch[x], AT.query(0, ch[x+X]-1)+1);
  }

  cout << max(AT.T[1], BT.T[1]) << '\n';
}

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