제출 #491714

#제출 시각아이디문제언어결과실행 시간메모리
491714mnair797Global Warming (CEOI18_glo)C++17
100 / 100
345 ms30148 KiB
#include <iostream>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
using namespace std;
 
typedef long long ll;
 
int dp1[200005];
int dp2[200005];
int niz[200005];
int bit[2000005];
 
cc_hash_table <int, int> u;
 
int getmax(int x){
    int res = 0;
    while(x){
        res = max(res, bit[x]);
        x -= x & -x;
    }
    return res;
}
 
void addbit(int x, int val){
    while(x <= 1000000){
        bit[x] = max(bit[x], val);
        x += x & -x;
    }
}
 
void clearbit(int n){
    for(int i=1; i<=n; i++) bit[i] = 0;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cout.precision(10);
    cout << fixed;
    
    int n, x;
    cin >> n >> x;
    vector <int> vec;
    for(int i=1; i<=n; i++){
        cin >> niz[i];
        vec.push_back(niz[i]);
        vec.push_back(niz[i] + x);
    }
    sort(vec.begin(), vec.end());
    int cnt = 0;
    for(auto c : vec){
        if(!u[c]) u[c] = ++cnt;
    }
    clearbit(cnt+5);
    for(int i=1; i<=n; i++){
        dp1[i] = 1 + getmax(u[niz[i]] - 1);
        addbit(u[niz[i]], dp1[i]);
    }
    clearbit(cnt+5);
    for(int i=n; i>=1; i--){
        dp2[i] = 1 + getmax(cnt+4-u[niz[i]] - 1);
        addbit(cnt+4-u[niz[i]], dp2[i]);
    }
    clearbit(cnt+5);
    int res = 0;
    for(int i=1; i<=n; i++){
        res = max(res, dp1[i]);
        res = max(res, dp2[i] + getmax(u[niz[i] + x] - 1));
        addbit(u[niz[i]], dp1[i]);
    }
    cout << res << "\n";
    return 0;
}
#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...