제출 #1097082

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1097082		Niosakaru	Global Warming (CEOI18_glo)	C++17	58 / 100	577 ms	11080 KiB

glo

#include <bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define N 200200

int n , x , p , fp , m , rt , l , r , mid , a[N] , b[N] , c[N] , d[N] , it[N << 2];
vector <int> vi;

void upd(int i,int l,int r,int p,int x){
    if (r < p || p < l) return;
    if (l == r) return it[i] = x, void();
    int mid = (l + r) >> 1;
    if (p <= mid) upd(i << 1,l,mid,p,x); else upd(i << 1|1,mid + 1,r,p,x);
    it[i] = max(it[i << 1] , it[i << 1|1]);  
}

int get(int i,int l,int r,int u,int v){
    if (v < l || r < u) return 0;
    if (u <= l && r <= v) return it[i];
    int mid = (l + r) >> 1;
    return max(get(i << 1,l,mid,u,v) , get(i << 1|1,mid + 1,r,u,v));
}

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

    cin >> n >> x;
    memset(d , 0x3f , sizeof d);
    for (int i = 1 ; i <= n ; i ++){
        cin >> a[i] , b[i] = lower_bound(d + 1,d + n + 1 , a[i]) - d; d[b[i]] = a[i];
        vi.push_back(a[i]) , vi.push_back(a[i] + x) , vi.push_back(a[i] - x);
    } 
    memset(d , 0 , sizeof d);
    for (int i = n ; i ; i --){
        l = 1 , r = n;
        while (l <= r){
            mid = (l + r) >> 1;
            if (d[mid] <= a[i]) p = mid , r = mid - 1; else l = mid + 1;
        } 
        c[i] = p , d[p] = a[i];
    }

    sort(vi.begin() , vi.end());
    vi.resize(unique(vi.begin() , vi.end()) - vi.begin());
    m = vi.size();

    for (int i = n ; i ; i --){
        p = lower_bound(vi.begin() , vi.end() , a[i]) - vi.begin() + 1 , fp = get(1 , 1 , m , p + 1 , m);
        rt = max(rt ,fp + b[i]);
        p = lower_bound(vi.begin() , vi.end() , a[i] + x) - vi.begin() + 1 , fp = get(1 , 1 , m , p + 1 , m);
        p = lower_bound(vi.begin() , vi.end() , a[i] + x) - vi.begin() + 1 , upd(1 , 1 , m , p , fp + 1);
    }
    memset(it , 0 , sizeof it);

    for (int i = n ; i ; i --){
        p = lower_bound(vi.begin() , vi.end() , a[i]) - vi.begin() + 1 , fp = get(1 , 1 , m , p + 1 , m);
        rt = max(rt ,fp + b[i]);
        p = lower_bound(vi.begin() , vi.end() , a[i] - x) - vi.begin() + 1 , fp = get(1 , 1 , m , p + 1 , m);
        p = lower_bound(vi.begin() , vi.end() , a[i] - x) - vi.begin() + 1 , upd(1 , 1 , m , p , fp + 1);
    }
    memset(it , 0 , sizeof it);

    for (int i = 1 ; i <= n ; i ++){
        p = lower_bound(vi.begin() , vi.end() , a[i]) - vi.begin() + 1 , fp = get(1 , 1 , m , 1 , p - 1);
        rt = max(rt ,fp + c[i]);
        p = lower_bound(vi.begin() , vi.end() , a[i] - x) - vi.begin() + 1 , fp = get(1 , 1 , m , 1 , p - 1);
        p = lower_bound(vi.begin() , vi.end() , a[i] - x) - vi.begin() + 1 , upd(1 , 1 , m , p , fp + 1);
    }
    memset(it , 0 , sizeof it);

    for (int i = 1 ; i <= n ; i ++){
        p = lower_bound(vi.begin() , vi.end() , a[i]) - vi.begin() + 1 , fp = get(1 , 1 , m , 1 , p - 1);
        rt = max(rt ,fp + c[i]);
        p = lower_bound(vi.begin() , vi.end() , a[i] + x) - vi.begin() + 1 , fp = get(1 , 1 , m , 1 , p - 1);
        p = lower_bound(vi.begin() , vi.end() , a[i] + x) - vi.begin() + 1 , upd(1 , 1 , m , p , fp + 1);
    }

    cout << rt << '\n';

    return 0;
}

/*

8 10
7 3 5 12 2 7 3 4

2
3
4
5
7
12
13
14
15
17
22

*/

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