Submission #1222101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222101		LaMatematica14	Global Warming (CEOI18_glo)	C++20	100 / 100	261 ms	15408 KiB

glo

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1<<18;
vector<int> seg(maxn<<1, 0);

int q(int a, int l, int r, int lq, int rq) {
    if (l >= lq && r <= rq) return seg[a];
    int mid = (l+r)/2;
    int x = 0;
    if (mid > lq) x = q(a<<1, l, mid, lq, rq);
    if (mid < rq) x = max(x, q(a<<1|1, mid, r, lq, rq));
    return x;
}

void upd(int a, int v) {
    for (a+=maxn; a > 0; a>>=1) seg[a] = max(seg[a], v);
}

int main() {
    int N, X; cin >> N >> X;
    vector<int> T(N);
    for (int i = 0; i < N; i++) cin >> T[i];

    vector<int> comp = T;
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    unordered_map<int, int> end;
    for (int i = 0; i < N; i++) end.insert({comp[i], i});


    // Right way LIS
    vector<int> pref(N);
    for (int i = 0; i < N; i++) {
        pref[i] = q(1, 0, maxn, 0, end[T[i]])+1;
        upd(end[T[i]], pref[i]);
    }

    // inverse LDS
    vector<int> S = T;
    reverse(S.begin(), S.end()); reverse(pref.begin(), pref.end());
    vector<int> dp(N+1, -1);
    int l = 1; dp[1] = 0;
    for (int i = 1; i < N; i++) {
        int fake = S[i]-X;
        if (S[dp[l]] > fake) pref[i] += l;
        else if (S[dp[1]] > fake) {
            int ll = 1, rr = N;
            while (ll  < rr-1) {
                int mid = (ll+rr)/2;
                if (S[dp[mid]] <= fake) rr = mid;
                else ll = mid;
            }
            pref[i] += ll;
        }

        if (S[dp[l]] > S[i]) dp[++l] = i;
        else if (S[dp[1]] <= S[i]) dp[1] = i;
        else {
            int ll = 1, rr = N;
            while (ll  < rr-1) {
                int mid = (ll+rr)/2;
                if (S[dp[mid]] <= S[i]) rr = mid;
                else ll = mid;
            }
            dp[rr] = i;
        }
    }
    int m = 0;
    for (int i = 0; i < N; i++) m = max(m, pref[i]);
    cout << m << '\n';
}

• 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