Submission #1338364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1338364		charlestitititit	Global Warming (CEOI18_glo)	C++20	100 / 100	40 ms	3116 KiB

glo

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

int a[200069];
int lis[200069], lds[200069];
vector<int> I, D;

signed main(){

    cin.tie(0); ios::sync_with_stdio(0);

    int n, x; cin >> n >> x;
    for(int i=1; i<=n; i++) cin >> a[i];

    int sz = 0;
    for(int i=1; i<=n; i++){
        int idx = lower_bound(I.begin(), I.end(), a[i]) - I.begin();
        if(idx == sz){
            I.push_back(a[i]);
            sz++;
        }
        else I[idx] = a[i];
        lis[i] = idx+1;
    }

    int mx = 0;
    sz = 0;

    for(int i=n; i>=1; i--){
        mx = max(mx, lis[i] + (int)(lower_bound(D.begin(), D.end(), -a[i] + x) - D.begin()));
        int idx = lower_bound(D.begin(), D.end(), -a[i]) - D.begin();
        if(idx == sz){
            D.push_back(-a[i]);
            sz++;
        }
        else D[idx] = -a[i];
    }

    cout << mx;

    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