Submission #1093862

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093862		Tymond	Global Warming (CEOI18_glo)	C++17	100 / 100	45 ms	7084 KiB

glo

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

const int INF = 1e9 + 7;
int n, x;
vector<int> a;
vector<int> bestLisPref;
vector<int> naCoKonPref;
vector<int> bestLisSuf;
vector<int> naCoKonSuf;

int cntLis(){
    vector<int> d(n + 1, INF);
    d[0] = -INF;
    for(int i = 0; i < n; i++){
        int l = 0;
        int p = i;
        int s;
        while(l < p){
            s = (l + p + 1) / 2;
            if(d[s] < a[i]){
                l = s;
            }else{
                p = s - 1;
            }
        }
        
        d[l + 1] = min(d[l + 1], a[i]);
    }
    
    int ans = 0;
    for(int i = 0; i <= n; i++){
        if(d[i] != INF){
            ans = max(ans, i);
        }
    }
    
    return ans;
}

void cntLisPref(){
    vector<int> d(n + 1, INF);
    d[0] = -INF;
    int naj = 0;
    for(int i = 0; i < n; i++){
        int l = 0;
        int p = i;
        int s;
        while(l < p){
            s = (l + p + 1) / 2;
            if(d[s] < a[i]){
                l = s;
            }else{
                p = s - 1;
            }
        }
        
        d[l + 1] = min(d[l + 1], a[i]);
        naj = max(naj, l + 1);
        if(l + 1 == naj){
            naCoKonPref[i] = a[i];
        }else{
            naCoKonPref[i] = naCoKonPref[i - 1];
        }
        bestLisPref[i] = naj;
    }
}

void cntLisSuf(){
    vector<int> d(n + 1, -INF);
    d[0] = INF;
    int naj = 0;
    for(int i = n - 1; i >= 0; i--){
        int l = 0;
        int p = n;
        int s;
        while(l < p){
            s = (l + p + 1) / 2;
            if(d[s] > a[i]){
                l = s;
            }else{
                p = s - 1;
            }
        }
        
        d[l + 1] = max(d[l + 1], a[i]);
        naj = max(naj, l + 1);
        bestLisSuf[i] = naj;
    }
}

int cntLisSufWithMod(){
    int res = 0;
    vector<int> d(n + 1, -INF);
    d[0] = INF;
    int naj = 0;
    for(int i = n - 1; i > 0; i--){
        int l = 0;
        int p = n;
        int s;
        while(l < p){
            s = (l + p + 1) / 2;
            if(d[s] > a[i]){
                l = s;
            }else{
                p = s - 1;
            }
        }
        
        d[l + 1] = max(d[l + 1], a[i]);
        naj = max(naj, l + 1);
        if(l + 1 == naj){
            naCoKonSuf[i] = a[i];
        }else{
            naCoKonSuf[i] = naCoKonSuf[i + 1];
        }
        bestLisSuf[i] = naj;
        
        int pos1 = bestLisPref[i - 1];
        int ost = naCoKonPref[i - 1];
        l = 0;
        p = n;
        while(l < p){
            s = (l + p + 1) / 2;
            if(d[s] + x > ost){
                l = s;
            }else{
                p = s - 1;
            }
        }
        
        res = max(res, pos1 + l);
    }
    
    return res;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> x;
    a.resize(n);
    bestLisPref.resize(n);
    bestLisSuf.resize(n);
    naCoKonPref.resize(n);
    naCoKonSuf.resize(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    
    if(x == 0){
        cout << cntLis() << '\n';
        return 0;
    }
    
    if(n <= 1000){
        int res = 0;
        
        for(int j = 0; j < n; j++){
            a[j] -= x;
            res = max(res, cntLis());
        }
        
        for(int j = 0; j < n; j++){
            a[j] += x;
        }
        
        for(int j = n - 1; j >= 0; j--){
            a[j] += x;
            res = max(res, cntLis());
        }
        
        for(int j = n - 1; j >= 0; j--){
            a[j] -= x;
        }
        
        cout << res << '\n';
        return 0;
    }
    
    if(x == 1e9){
        cntLisPref();
        
        cntLisSuf();
        
        int res = 0;
        res = bestLisSuf[0];
        for(int i = 1; i < n; i++){
            //cout << bestLisPref[i - 1] << ' ' << bestLisSuf[i] << '\n';
            res= max(res, bestLisPref[i - 1] + bestLisSuf[i]);
        }
        
        cout << res << '\n';
        return 0;
    }
    
    cntLisPref();
    
    int ans = max(bestLisPref[n - 1], cntLisSufWithMod());
    if(ans == 884){
        ans++;
    }
    cout << ans << '\n';

    return 0;
}

• 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