Submission #1203922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203922		julia_08	Global Warming (CEOI18_glo)	C++20	100 / 100	293 ms	72512 KiB

glo

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int MAXN = 2e5 + 10;
const int INF = 1e9 + 1;

int a[MAXN];

int dp[MAXN], lis[MAXN][2];

int n;

vector<int> seg, lc, rc;

int create(){
  seg.push_back(0);
  lc.push_back(0);
  rc.push_back(0);
  return seg.size() - 1;
}

void update(int x, int lx, int rx, int i, int val){

  if(lx == rx){
    seg[x] = max(seg[x], val);
    return;
  }

  int m = (lx + rx) >> 1;

  if(i <= m){
    if(lc[x] == 0){
      int aux = create();
      lc[x] = aux;
    }

    update(lc[x], lx, m, i, val);

  } else{
    if(rc[x] == 0){
      int aux = create();
      rc[x] = aux;
    }

    update(rc[x], m + 1, rx, i, val);
  }

  seg[x] = max(seg[lc[x]], seg[rc[x]]);
}

int query(int x, int lx, int rx, int l, int r){

  if(rx < l || lx > r) return 0;

  if(l <= lx && rx <= r) return seg[x];

  int m = (lx + rx) >> 1;
  return max(query(lc[x], lx, m, l, r), query(rc[x], m + 1, rx, l, r));
}

void inv(){
  for(int i=1; i<=n; i++) a[i] = -a[i];
  reverse(a + 1, a + n + 1);
}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);

  int x; cin >> n >> x;

  for(int i=1; i<=n; i++) cin >> a[i];

  for(int i=1; i<=n; i++) dp[i] = INF;

  for(int i=1; i<=n; i++){

    int l = lower_bound(dp + 1, dp + n + 1, a[i]) - dp;

    dp[l] = a[i];
    lis[i][0] = l;

  }

  inv();

  for(int i=1; i<=n; i++) dp[i] = INF;

  for(int i=1; i<=n; i++){

    int l = lower_bound(dp + 1, dp + n + 1, a[i]) - dp;

    dp[l] = a[i];
    lis[n - i + 1][1] = l;

  }

  inv();

  int ans = 0;

  create();
  create();

  for(int i=1; i<=n; i++){
    ans = max(ans, query(1, 1, INF, 1, min(INF, a[i] + x - 1)) + lis[i][1]);
    update(1, 1, INF, a[i], lis[i][0]);
  }

  cout << ans << "\n";

  return 0;
}

• 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