Submission #785262

#	Time	Username	Problem	Language	Result	Execution time	Memory
785262		andecaandeci	Global Warming (CEOI18_glo)	C++17	55 / 100	2057 ms	6108 KiB

glo

#include <bits/stdc++.h>
using namespace std;

# define int long long
# define fir first
# define sec second
# define pb push_back
# define endl "\n"

const int cnst = 2e5+5;
bool mutipletestcase = 0;
//bool debug = false;

void solve() {
    int n, x; cin >> n >> x;

    int num[n+5];

    for(int i = 1; i<=n; i++) cin >> num[i];

    if(x == 0) {
        vector<int> vec; vec.pb(num[1]);

        for(int i = 2; i<=n; i++) {
            if(num[i] > vec[vec.size()-1]) {vec.pb(num[i]); continue;}

            int lo = 0;
            int hi = vec.size()-1;
            int res = vec.size()-1;
            
            while(lo <= hi) {
                int mid = (lo+hi)/2;

                // cerr << "I: " << vec[mid] << " " << num[i] << endl;
                if(vec[mid] < num[i]) lo = mid+1;
                else hi = mid-1, res = mid;
            }

            // cerr << i << " " << res << endl;
            vec[res] = num[i];
        }

        // for(auto v: vec) cerr << v << " ";
        cout << vec.size() << endl;
        return;
    }
    else if(x == 1e9) {
        int l[n+5], r[n+5]; l[1] = 1; l[0] = 0;
        vector<int> vec; vec.pb(num[1]);

        for(int i = 2; i<=n; i++) {
            if(num[i] > vec[vec.size()-1]) {vec.pb(num[i]); l[i] = vec.size(); continue;}

            int lo = 0;
            int hi = vec.size()-1;
            int res = vec.size()-1;
            
            while(lo <= hi) {
                int mid = (lo+hi)/2;

                // cerr << "I: " << vec[mid] << " " << num[i] << endl;
                if(vec[mid] < num[i]) lo = mid+1;
                else hi = mid-1, res = mid;
            }

            // cerr << i << " " << res << endl;
            vec[res] = num[i];
            l[i] = vec.size();
        }

        vec.clear();
        vec.pb(num[n]); r[n] = 1, r[n+1] = 0;

        for(int i = n-1; i>=1; i--) {
            if(num[i] < vec[vec.size()-1]) {vec.pb(num[i]); r[i] = vec.size(); continue;}

            int lo = 0;
            int hi = vec.size()-1;
            int res = vec.size()-1;
            
            while(lo <= hi) {
                int mid = (lo+hi)/2;

                // cerr << "I: " << vec[mid] << " " << num[i] << endl;
                if(vec[mid] > num[i]) lo = mid+1;
                else hi = mid-1, res = mid;
            }

            // cerr << i << " " << res << endl;
            vec[res] = num[i];
            r[i] = vec.size();
        }

        // for(int i = 1; i<=n; i++) cerr << l[i] << " "; cerr << endl;
        // for(int i = 1; i<=n; i++) cerr << r[i] << " "; cerr << endl;

        int ans = 0;

        for(int i = 0; i<=n; i++) {
            ans = max(ans, l[i]+r[i+1]);
        }

        cout << ans << endl;
        return;
    }

    int ans = 0;
    int dp[n+5][3];
    memset(dp, 0, sizeof(dp)); dp[n][1] = dp[n][0] = 1;

    for(int i = n-1; i>=1; i--) {
        for(int k = i+1; k<=n; k++) {
            if(num[k] > num[i]) {
                dp[i][0] = max(dp[i][0], dp[k][0]);
                dp[i][1] = max(dp[i][1], dp[k][1]);
            }
            else if(num[i]-num[k] < x) {
                dp[i][0] = max(dp[i][0], dp[k][1]);
            }
        }

        dp[i][0] += 1, dp[i][1] += 1;
        ans = max(ans, dp[i][0]);
    }    

    // for(int i = 1; i<=n; i++) cerr << dp[i][0] << " " << dp[i][1] << endl; cerr << endl;

    cout << ans << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    int t = 1;
    if(mutipletestcase) cin >> t; 
    while(t--) solve();
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 17 / 17
• Subtask 7: 0 / 25