Submission #1085515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085515		vjudge1	Global Warming (CEOI18_glo)	C++17	100 / 100	95 ms	11808 KiB

glo

#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define int long long
#define ar array


const int N = 2e5 + 20;

namespace fewwy{
    int bit[2][N];
    template<int x>
    int qry(int i){
        int ans = 0;
        for(i++;i;i -= i & -i)ans = max(ans,bit[x][i]);
        return ans;
    }

    template<int x>
    void upd(int i,int v){
        for(i++;i < N;i += i & -i)bit[x][i] = max(bit[x][i], v);
    }
}

vector<int> v;
int get(int x){
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

signed main() {ios_base::sync_with_stdio(false);cin.tie(0);
    int n, x;
    cin>>n>>x;
    int A[n];
    for(int i =0 ;i < n;i++){
        cin>>A[i];
        v.push_back(A[i]);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    int ans = 0;
    int dp[n][2];
    for(int i = 0;i < n;i++){
        int y = get(A[i]);
        dp[i][0] = fewwy::qry<0>(y - 1) + 1;
        dp[i][1] = max(fewwy::qry<1>(y - 1), fewwy::qry<0>(get(A[i] + x) - 1)) + 1;
        fewwy::upd<0>(y, dp[i][0]);
        fewwy::upd<1>(y, dp[i][1]);
        ans = max({ans, dp[i][0], dp[i][1]});
    }
    cout<<ans;
}

• 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