Submission #1097037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097037		Niosakaru	Global Warming (CEOI18_glo)	C++17	58 / 100	297 ms	9476 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 , a[N] , b[N] , c[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 p){
    if (r < p) return 0;
    if (l >= p) return it[i];
    int mid = (l + r) >> 1;
    return max(get(i << 1,l,mid,p) , get(i << 1|1,mid + 1,r,p));
}

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

    cin >> n >> x;
    memset(c , 0x3f , sizeof c);
    for (int i = 1 ; i <= n ; i ++){
        cin >> a[i] , b[i] = lower_bound(c + 1,c + n + 1 , a[i]) - c; c[b[i]] = a[i];
        vi.push_back(a[i]) , vi.push_back(a[i] + x) , vi.push_back(a[i] - x);
    } 

    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);
        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);
        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);
        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);
        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