Submission #97272

#	Time	Username	Problem	Language	Result	Execution time	Memory
97272		dalgerok	Global Warming (CEOI18_glo)	C++14	100 / 100	425 ms	12744 KiB

glo

#include<bits/stdc++.h>
using namespace std;


const int N = 2e5 + 5;



int n, d, a[N], b[N], val[N];
int t[8 * N];
vector < int > e;

void update(int v, int l, int r, int pos, int x){
    if(l == r){
        t[v] = max(t[v], x);
        return;
    }
    int mid = (r + l) >> 1;
    if(pos <= mid){
        update(v + v, l, mid, pos, x);
    }
    else{
        update(v + v + 1, mid + 1, r, pos, x);
    }
    t[v] = max(t[v + v], t[v + v + 1]);
}
int get(int v, int l, int r, int tl, int tr){
    if(l > r || l > tr || tl > r || tl > tr){
        return 0;
    }
    if(tl <= l && r <= tr){
        return t[v];
    }
    int mid = (r + l) >> 1;
    return max(get(v + v, l, mid, tl, tr), get(v + v + 1, mid + 1, r, tl, tr));
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> d;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        e.push_back(a[i]);
        e.push_back(a[i] + d);
    }
    sort(e.begin(), e.end());
    e.resize(unique(e.begin(), e.end()) - e.begin());
    for(int i = 1; i <= n; i++){
        b[i] = lower_bound(e.begin(), e.end(), a[i] + d) - e.begin() + 1;
        a[i] = lower_bound(e.begin(), e.end(), a[i]) - e.begin() + 1;
    }
    int sz = (int)e.size();
    for(int i = n; i >= 1; i--){
        update(1, 1, sz, b[i], (val[i] = get(1, 1, sz, b[i] + 1, sz) + 1));
    }
    int ans = t[1];
    memset(t, 0, sizeof(t));
    for(int i = 1; i <= n; i++){
        ans = max(ans, get(1, 1, sz, 1, b[i] - 1) + val[i]);
        update(1, 1, sz, a[i], get(1, 1, sz, 1, a[i] - 1) + 1);
    }
    cout << ans;
}

• 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