제출 #166132

#제출 시각아이디문제언어결과실행 시간메모리
166132GustavKGlobal Warming (CEOI18_glo)C++14
75 / 100
1678 ms10204 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;
}

vl A;
int dp[100000];
int LIS2(int pos){
    if(dp[pos] != -1) return dp[pos];
    int r = 0;
    for(int i = pos+1; i < sz(A); i++){
        if(A[i] > A[pos])
            r = max(r, LIS2(i));
    }
    return dp[pos] = r + 1;
}

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){
        ans = 0;
        for(int i = n-1; i >= 0; i--){
            a[i] += x;
            A = a;
            memset(dp, -1, sizeof(dp));
            for(int j = 0; j < n; j++)
                ans = max(ans, LIS2(j));
        }
    }

    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...