Submission #920214

#	Time	Username	Problem	Language	Result	Execution time	Memory
920214		Mathii3u	Global Warming (CEOI18_glo)	C++14	0 / 100	48 ms	8016 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;

mll moves(vll t , vi & action) {
    rev(t);
    mll dp;
    auto comp = [](const vll &x, const vll &y)
    {
        return x.back() > y.back();
    };

    FOR(i, 0, sz(t))
    {
        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;
            }
        }

        action[i] = id;
        if (id == sz(dp)) {
            dp.pb({t[i]});
        } else {
            dp[id].pb(t[i]);
        }
    }
    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);
    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;
            }
        }
    }
    cout << best << endl;
    return 0;
}

Compilation message (stderr)

glo.cpp: In function 'std::vector<std::vector<long long int> > moves(std::vector<long long int>, std::vector<int>&)':
glo.cpp:41:10: warning: variable 'comp' set but not used [-Wunused-but-set-variable]
   41 |     auto comp = [](const vll &x, const vll &y)
      |          ^~~~

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