제출 #1234759

#제출 시각아이디문제언어결과실행 시간메모리
1234759dssfsuper2Global Warming (CEOI18_glo)C++20
100 / 100
511 ms26248 KiB

#include <bits/stdc++.h>
using namespace std;
struct Fenwick{
    vector<int> bit;
    int n;
    Fenwick(int N) {
        n=N;
        bit.assign(n, 0);
    }
    int getmax(int r) {
        int ret = 0;
        if(r<0)return 0;
        for (;r>=0;r=(r&(r+1))-1)
            ret = max(ret, bit[r]);
        return ret;
    }

    void update(int i, int v) {
        for (;i<n;i=i|(i+1))
            bit[i] = max(bit[i], v);
    }
};
int dp[200001][2];
signed main(){
    int n,x;cin>>n>>x;
    vector<int> a(n);
    for(int i = 0;i<n;i++){
        cin>>a[i];
    }
    //coordinate compress
    map<int, int> compressed;
    vector<int> b=a;
    for(auto thing:a){
        b.push_back(thing+x);
    }
    sort(b.begin(), b.end());
    for(int i = 0;i<b.size();i++){
        compressed[b[i]]=i;
    }
    Fenwick fenw0(b.size()), fenw1(b.size());
    for(int i = 0;i<n;i++){
        dp[i][1]=max(fenw0.getmax(compressed[a[i]+x]-1), fenw1.getmax(compressed[a[i]]-1))+1;
        fenw1.update(compressed[a[i]], dp[i][1]);
        dp[i][0]=fenw0.getmax(compressed[a[i]]-1)+1;
        fenw0.update(compressed[a[i]], dp[i][0]);
        

    }
    int res = 0;
    for(int i = 0;i<n;i++){
        //cout << dp[i][0] << ' ';
        res=max(res, dp[i][0]);
        res=max(res, dp[i][1]);
    }
    //cout << '\n';
    //for(int i = 0;i<n;i++)cout << dp[i][1] << ' ';
    //cout << '\n';
    cout << res << '\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...