Submission #422509

#	Time	Username	Problem	Language	Result	Execution time	Memory
422509		Emin2004	Global Warming (CEOI18_glo)	C++14	100 / 100	133 ms	14696 KiB

glo

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

#define endl '\n'
#define pii pair <ll, int>
#define pb push_back
#define F first
#define S second
#define ll long long
#define io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define M_PI 3.14159265358979323846

const int N = 200005;
const int mod = 1e9 + 7;

ll lis[N], lds[N], a[N];
ll mp[N];

int main() {
    io;
    ll n, d;
    cin >> n >> d;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        mp[i + 1] = INT_MAX;
    }
    ll ans = 0;
    mp[1] = a[0];
    lis[0] = 1;
    for(int i = 1; i < n; i++){
        ll l = 1, r = n;
        lis[i] = 1;
        while(l <= r){
            ll mid = (l + r) / 2;
            if(mp[mid] < a[i]){
                mp[mid + 1] = min(mp[mid + 1], a[i]);
                lis[i] = max(lis[i], mid + 1);
                l = mid + 1;
                ans = max(ans, l);
            }
            else{
                r = mid - 1;
            }
        }
        mp[1] = min(mp[1], a[i]);
    }
    if(d == 0){
        cout << ans;
        return 0;
    }
    for(int i = 1; i <= n; i++){
        mp[i] = 0;
    }
    mp[1] = a[n - 1];
    lds[n - 1] = 1;
    for(int i = n - 2; i >= 0; i--){
        ll l = 1, r = n;
        lds[i] = 1;
        while(l <= r){
            ll mid = (l + r) / 2;
            if(mp[mid] > a[i]){
                mp[mid + 1] = max(mp[mid + 1], a[i]);
                lds[i] = max(lds[i], mid + 1);
                l = mid + 1;
            }
            else{
                r = mid - 1;
            }
        }
        mp[1] = max(mp[1], a[i]);
    }
    for(int i = 1; i <= n; i++){
        mp[i] = -1;
    }
    set<pii> s;
    s.insert({a[0], 1});
    mp[1] = a[0];
    for(int i = 1; i < n; i++){
        ll cur = lds[i];
        ll k = a[i] + d;
        set<pii>::iterator itr = s.lower_bound({k, 0});
       // cout << (*itr).F << " " << " " << lis[i] << " ";
        if(itr != s.begin()) itr--;
        else cur = INT_MIN;
        cur += (*itr).S;
        if(mp[lis[i]] > a[i]){
            s.erase(s.find({mp[lis[i]], lis[i]}));
            s.insert({a[i], lis[i]});
            mp[lis[i]] = a[i];
        }
        if(mp[lis[i]] == -1){
            s.insert({a[i], lis[i]});
            mp[lis[i]] = a[i];
        }
        //if(i == 4) cout << cur << " " ;
        ans = max(ans, cur);
    }
    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