제출 #1302457

#제출 시각아이디문제언어결과실행 시간메모리
1302457nathlol2Global Warming (CEOI18_glo)C++20
10 / 100
478 ms169200 KiB
#include <bits/stdc++.h>
using namespace std;
const int N = 222222, MX = 2e9;
int n, k, ans, a[N];

struct seg{
    struct node{
        node *l, *r;
        int v;
        node(int v):v(v), l(0), r(0){}
    };
    typedef node* pnode;
    pnode rt = 0;
    void upd(pnode &k, int l, int r, int pos, int x){
        if(!k) k = new node(0);
        if(l == r) return k->v = x, void();
        int md = (l + r) / 2;
        if(pos <= md) upd(k->l, l, md, pos, x);
        else upd(k->r, md + 1, r, pos, x);
        k->v = max(k->l ? k->l->v : 0, k->r ? k->r->v : 0);
    }
    int qry(pnode k, int l, int r, int ql, int qr){
        if(!k || r < ql || qr < l) return 0;
        if(ql <= l && r <= qr) return k->v;
        int md = (l + r) / 2;
        return max(qry(k->l, l, md, ql, qr), qry(k->r, md + 1, r, ql, qr)); 
    }
}s, s1;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k;
    for(int i = 1;i<=n;i++) cin >> a[i];
    for(int i = 1;i<=n;i++){
        int d = s.qry(s.rt, 1, MX, 1, a[i] - 1);
        int d1 = s.qry(s.rt, 1, MX, 1, a[i] + k - 1);
        s.upd(s.rt, 1, MX, a[i], d + 1);
        s1.upd(s1.rt, 1, MX, a[i], d1 + 1);
        ans = max(ans, d1 + 1);
        ans = max(ans, s1.qry(s1.rt, 1, MX, 1, a[i] - 1) + 1);
    }
    cout << ans;
}
#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...