Submission #1146863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146863		MladenP	Global Warming (CEOI18_glo)	C++20	100 / 100	998 ms	52080 KiB

glo

#include<bits/stdc++.h>
#define STIZE(x) fprintf(stderr, "STIZE%d\n", x);
#define PRINT(x) fprintf(stderr, "%s = %d\n", #x, x);
#define NL(x) printf("%c", " \n"[(x)]);
#define lld long long
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define all(a) begin(a),end(a)
#define sz(a) int((a).size())
#define LINF 1000000000000000
#define INF 1000000000
#define EPS 1e-9
#define mid (l+r)/2
#define endl '\n'
using namespace std;
#define MAXN 200010
lld N, X, idx = 0;
lld a[MAXN], bit[3*MAXN], lisl[MAXN], lisr[MAXN], rev[3*MAXN];
map<lld,lld> hsh;
void update(int idx, lld val) {
    while(idx < 3*MAXN) {
        bit[idx] = max(bit[idx], val);
        idx += idx&-idx;
    }
}
lld query(int idx) {
    lld rez = 0;
    while(idx > 0) {
        rez = max(rez, bit[idx]);
        idx -= idx&-idx;
    }
    return rez;
} 
int main() {
    cin >> N >> X;
    for(int i = 1; i <= N; i++) {
        cin >> a[i];
        hsh[a[i]] = 0;
        hsh[a[i]+X] = 0;
        hsh[a[i]-X] = 0;
    }
    for(auto x : hsh) hsh[x.fi] = ++idx, rev[idx] = x.fi;
    for(int i = 1; i <= N; i++) a[i] = hsh[a[i]];

    lisl[0] = 0;
    for(int i = 1; i <= N; i++) {
        lisl[i] = query(a[i]-1) + 1;
        update(a[i], lisl[i]);
    }
    fill(bit, bit+3*MAXN, 0);

    lisr[N+1] = 0;
    for(int i = N; i >= 1; i--) {
        lisr[i] = query(3*MAXN-a[i]-1) + 1;
        update(3*MAXN-a[i], lisr[i]);
    }
    fill(bit, bit+3*MAXN, 0);

    lld rez = 0;
    for(int i = 1; i <= N; i++) rez = max(rez, lisl[i]);
    for(int i = 1; i <= N; i++) {
        int ispod = hsh[rev[a[i]]+X];
        rez = max(rez, lisr[i] + query(ispod-1));
        update(a[i], lisl[i]);
    }
    fill(bit, bit+3*MAXN, 0);

    for(int i = N; i >= 1; i--) {
        int iznad = hsh[rev[a[i]]-X];
        rez = max(rez, lisl[i] + query(3*MAXN-iznad-1));
        update(3*MAXN-a[i], lisr[i]);
    }
    cout << rez;
    return 0;
}

• 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