제출 #166128

#제출 시각아이디문제언어결과실행 시간메모리
166128GustavKGlobal Warming (CEOI18_glo)C++14
62 / 100
169 ms8876 KiB
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pi> vpi;
typedef vector<vi> vvi;
const int inf = 0x3f3f3f3f;
const ll linf = 123456789012345678;
const ll mod = 1000000007;
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << endl
#define sz(x) ((int)(x).size())

int LIS(vl a){
    vl b(200010, linf);
    int r = 0;
    for(int i = 0; i < sz(a); i++){
        auto p = lower_bound(all(b), a[i]);
        if(*p == linf) r++;
        *p = a[i];
    }
    return r;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
	
    ll n, x;
    cin >> n >> x;
    vl a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    vl b(200010, linf);
    stack<pair<ll,ll>> undo;
    for(int i = n-1; i >= 0; i--){
        int p = lower_bound(all(b), -a[i]-x) - b.begin();
        undo.emplace(p, b[p]);
        b[p] = -a[i]-x;
    }

    vl c(200010, linf);
    int len = 0;
    int ans = 0;
    for(int i = 0; i < n; i++){
        b[undo.top().first] = undo.top().second;
        undo.pop();

        int p = lower_bound(all(c), a[i]) - c.begin();
        if(c[p] == linf) len++;
        if(p+1 == len){
            ans = max(ans, len + (int)(lower_bound(all(b), -a[i]) - b.begin()));
        }
        c[p] = a[i];
    }

    if(n <= 1000){
        int ans = 0;
        for(int i = n-1; i >= 0; i--){
            a[i] += x;
            ans = max(ans, LIS(a));
        }
    }

    cout << ans << "\n";
}
#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...