제출 #1314619

#제출 시각아이디문제언어결과실행 시간메모리
1314619AblablaGlobal Warming (CEOI18_glo)C++20
100 / 100
100 ms8268 KiB
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;

    vector<int> alap(n);
    for(int &x : alap){
        cin >> x;
    }

    vector<vector<int>> csokk;
    vector<int> hely(n);
    for(int i = n - 1; i >= 0; i--){
        int l = 0, r = csokk.size() - 1;
        int ind = -1;
        while(l <= r){
            int k = (l + r) / 2;

            if(alap[i] >= csokk[k].back()){
                ind = k;
                r = k - 1;
            } else{
                l = k + 1;
            }
        }

        if(ind == -1){
            hely[i] = csokk.size();
            csokk.push_back(vector<int>({alap[i]}));
        } else{
            csokk[ind].push_back(alap[i]);
            hely[i] = ind;
        }
    }

//    vector<int> index(csokk.size());
//    for(int i = 0; i < csokk.size(); i++){
//        index[i] = csokk[i].size() - 1;
//    }

    int ans = 0;
    //int hossz = csokk.size();

    //cout << csokk.size() << "\n";

    vector<int> no;
    for(int i = 0; i < n; i++){
        /*index[hely[i]]--;

        if(index[hely[i]] == -1){
            hossz--;
        }*/
        csokk[hely[i]].pop_back();

        if(csokk.back().size() == 0){
            csokk.pop_back();
        }




        auto it = lower_bound(no.begin(), no.end(), alap[i]);
        int hossz = it - no.begin();

        if(it == no.end()){
            no.push_back(alap[i]);
        } else{
            *it = alap[i];
        }


        int l = 0, r = csokk.size() - 1;
        int ind = -1;
        while(l <= r){
            int k = (l + r) / 2;

            if(alap[i] - m < csokk[k].back()){
                ind = k;
                l = k + 1;
            } else{
                r = k - 1;
            }
        }

        ans = max(ans, hossz + ind + 2);
    }

    //cout << no.size() << "\n";
    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...