Submission #1234759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234759		dssfsuper2	Global Warming (CEOI18_glo)	C++20	100 / 100	511 ms	26248 KiB

glo

#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';
}

• 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