Submission #501545

#	Time	Username	Problem	Language	Result	Execution time	Memory
501545		sberens	Global Warming (CEOI18_glo)	C++17	27 / 100	75 ms	8512 KiB

glo

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
template<typename K> using hset = gp_hash_table<K, null_type>;
template<typename K, typename V> using hmap = gp_hash_table<K, V>;


using namespace std;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define smax(x, y) (x = max(x, y))
#define smin(x, y) (x = min(x, y))

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i,0,a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i,0,a)


using ll = long long;
using ld = long double;

template<typename T>
using vv = vector<vector<T>>;

using vi = vector<int>;
using ii = array<int, 2>;
using vii = vector<ii>;
using vvi = vv<int>;

using vll = vector<ll>;
using l2 = array<ll, 2>;
using vl2 = vector<l2>;
using vvll = vv<ll>;

template<typename T>
using minq = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using maxq = priority_queue<T>;

template<typename T>
using oset = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;

const ll M = 1000000007;
const ll infll = M * M;

template<typename IN>
IN discrete_binary_search(function<bool(IN)> predicate, IN low = 0, IN high = numeric_limits<IN>::max()) {
    while (low < high) {
        IN middle = low + (high - low) / 2; // todo std::midpoint in cpp 2020
        if (predicate(middle))
            high = middle;
        else low = middle + 1;
    }
    return low;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll n, x;
    cin >> n >> x;
    vll t(n);
    F0R(i, n) cin >> t[i];
    vi plis(n), slds(n);
    vll idp(n+1, infll);
    idp[0] = -infll;
    F0R(i, n) {
        *lower_bound(all(idp), t[i]-x) = t[i]-x;
        plis[i] = lower_bound(all(idp), t[i]) - idp.begin();
    }
    vll ddp(n+1, -infll);
    ddp[0] = infll;
    R0F(i, n) {
        int j = discrete_binary_search<int>([&](int j) -> bool {
            return ddp[j] <= t[i];
        }, 0, n);
        ddp[j] = t[i];
        slds[i] = j;
    }
    int res = -1;
    F0R(i, n) smax(res, plis[i] + slds[i] -1);
    cout << res << '\n';
}

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