Submission #467951

#	Time	Username	Problem	Language	Result	Execution time	Memory
467951		ivan_tudor	Global Warming (CEOI18_glo)	C++14	100 / 100	1041 ms	129848 KiB

glo

#include<bits/stdc++.h>
using namespace std;
const int VMAX = 1e9;
struct aintnode{
  int l, r;
  int mval;
  aintnode *ls, *rs;
  aintnode(int _l, int _r){
    l = _l;
    r = _r;
    mval = 0;
    ls = rs  = NULL;
  }
};
void update(aintnode *node, int poz, int val){
  int l = node->l, r = node->r;
  if(poz < l || poz > r)
    return;
  if(l == r){
    node->mval = val;
    return;
  }
  int mid = (l + r)/2;
  if(poz <= mid){
    if(node->ls == NULL)
      node->ls = new aintnode(l, mid);
    update(node->ls, poz, val);
  }
  else{
    if(node->rs == NULL)
      node->rs = new aintnode(mid +1, r);
    update(node->rs, poz, val);
  }
  node->mval = 0;
  if(node->ls != NULL)
    node->mval = max(node->mval, node->ls->mval);
  if(node->rs != NULL)
    node->mval = max(node->mval, node->rs->mval);
}
int query(aintnode *node, int ql, int qr){
  if(node == NULL)
    return 0;
  if(qr < node->l || ql > node->r)
    return 0;
  if(ql <= node->l && node->r <= qr)
    return node->mval;
  return max(query(node->ls, ql, qr), query(node->rs, ql, qr));
}
void clr(aintnode *node){
  if(node->ls != NULL)
    clr(node->ls);
  if(node->rs != NULL)
    clr(node->rs);
  delete node;
}
const int N = 200005;
int v[N];
int r[N];
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n, d;
  cin>>n>>d;
  for(int i = 1; i<=n; i++){
    cin>>v[i];
  }
  aintnode *root = new aintnode(1, VMAX);
  for(int i = n; i>=1; i--){
    int lenmax = query(root, v[i] + 1, VMAX);
    r[i] = lenmax + 1;
    update(root, v[i], r[i]);
  }
  clr(root);
  root = new aintnode(1, VMAX);
  int ans = 0;
  for(int i = 1; i<=n; i++){
    int lmaxd = query(root, 1, v[i] + d - 1);
    ans = max(ans, lmaxd + r[i]);
    int lenm = query(root, 1, v[i] - 1);
    update(root, v[i], lenm + 1);
  }
  cout<<ans;
  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