제출 #920235

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
920235		Mathii3u	Global Warming (CEOI18_glo)	C++14	62 / 100	50 ms	13824 KiB

glo

//#include <bits/myh.h>
#include<bits/stdc++.h>

// prime : M_19 5e6 , M_31 2e10
// __builtin_popcount , __builtin_ctz
// ./exec < input.txt 2> stderr.txt > stdout.txt 

using ull = unsigned long long;
using ll = long long;
using ld = long double;
using namespace std;
#define endl "\n";
#define F first
#define S second
#define ALL(a) a.begin(),a.end()
#define MP make_pair
#define pb push_back
#define BigInt __int128;
#define vi vector<int>
#define vpi vector<pi>
#define mi vector<vector<int>>
#define pi pair<int,int>
#define vll vector<ll>
#define mll vector<vll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define FOR(i, a, b) for (int i = a; i < b;i++)
#define FORS(i, a, b,step) for (int i = a; i < b;i += step)
#define sz(x) (int)x.size()
#define rev(v) reverse(v.begin(),v.end())
#define ITER(x,a) for(auto x : a )
#define sort_incr(a) sort(a.begin(),a.end())
#define sort_decr(a) sort(a.rbegin(),a.rend())
const ll MOD = 1e9 + 7;
int T;
int cases;

void print_state(mll & dp) {
    ITER(x,dp) {
        cout << x.back() << " ";
    }
    cout << endl;
}

void print_vll(vll & dp) {
    ITER(x,dp) {
        cout << x << " ";
    }
    cout << endl;
}

mll moves(vll t , vi & action) {
    rev(t);
    mll dp;
    FOR(i, 0, sz(t))
    {
        //print_state(dp);
        int id = sz(dp);
        int deb = 0;
        int fin = sz(dp);
        while(deb < fin) {
            int mid = (deb + fin) / 2;
            if (t[i] < dp[mid].back()) {
                deb = mid + 1;
            } else {
                id = mid;
                fin = mid;
            }
        }
        //cout << i << "-> " << id << endl;

        action[i] = id;
        if (id == sz(dp)) {
            dp.pb({t[i]});
        } else {
            dp[id].pb(t[i]);
        }
    }
    // print_state(dp);
    // cout << endl;
    return dp;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n, x;
    cin >> n >> x;
    vll t(n);
    FOR(i, 0, n)
        cin >> t[i];

    vi action(n);
    mll dp_rev = moves(t, action);
    vll dp;
    ll best = sz(dp_rev);
    //print_state(dp_rev);
    FOR(i, 0, n - 1)
    {
        // maj [0;i]
        int id = lower_bound(dp.begin(), dp.end(), t[i]) - dp.begin();
        if (id == sz(dp)) {
            dp.pb(t[i]);
        } else {
            dp[id] = t[i];
        }

        // maj ]i;n-1]
        if (sz(dp_rev[action[n - 1 - i]]) == 1)
        {
            dp_rev.pop_back();
        } else {
            dp_rev[action[n - 1 - i]].pop_back();
        }

        ll sup_left = dp.back();
        ll deb = 0;
        ll fin = sz(dp_rev);
        while(deb < fin) {
            ll mid = (deb + fin) / 2;
            if (dp_rev[mid].back()+x > sup_left  ) {
                best = max(best, mid + 1 + sz(dp));
                deb = mid + 1;
            } else {
                fin = mid;
            }
        }

        ll sup_right = dp_rev.back().back();
        deb = 0;
        fin = sz(dp);
        while(deb < fin) {
            ll mid = (deb + fin) / 2;
            if (sup_right+x > dp[mid]  ) {
                best = max(best, mid + 1 + sz(dp_rev));
                deb = mid + 1;
            } else {
                fin = mid;
            }
        }
        //print_state(dp_rev);
    }
    //print_state(dp_rev);
    cout << best << endl;
    return 0;
}

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