Submission #901953

#	Time	Username	Problem	Language	Result	Execution time	Memory
901953		Ghetto	Global Warming (CEOI18_glo)	C++17	75 / 100	553 ms	159696 KiB

glo

#include <bits/stdc++.h>   
using namespace std;
const int MAX_N = 2e5 + 5, MAX_LOG_ARR = 30 + 2, MAX_ARR = 1e9;

int n, x;
int arr[MAX_N];

int l_dp[MAX_N], r_dp[MAX_N];

int segtree[MAX_N * MAX_LOG_ARR]; // Test
int n_nodes;
int l_child[MAX_N * MAX_LOG_ARR], r_child[MAX_N * MAX_LOG_ARR];
void init() {
    for (int i = 1; i <= n_nodes; i++) {
        segtree[i] = 0;
        l_child[i] = r_child[i] = 0;
    }
    n_nodes = 1;
}
void propogate(int u) {
    if (l_child[u]) return;

    n_nodes++;
    l_child[u] = n_nodes;
    n_nodes++;
    r_child[u] = n_nodes;
}
void update(int i, int val, int u = 1, int lo = 0, int hi = MAX_ARR) {
    if (lo == hi) {
        segtree[u] = val;
        return;
    }

    propogate(u);
    int mid = (lo + hi) / 2;
    if (i <= mid) update(i, val, l_child[u], lo, mid);
    else update(i, val, r_child[u], mid + 1, hi);
    segtree[u] = max(segtree[l_child[u]], segtree[r_child[u]]);
}
int query(int l, int r, int u = 1, int lo = 0, int hi = MAX_ARR) {
    if (l <= lo && hi <= r) 
        return segtree[u];

    propogate(u);
    int mid = (lo + hi) / 2, ans = 0;
    if (l <= mid) ans = max(ans, query(l, r, l_child[u], lo, mid));
    if (r > mid) ans = max(ans, query(l, r, r_child[u], mid + 1, hi));
    return ans;
}

int main() {
    // freopen("global.in", "r", stdin);

    cin >> n >> x;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];

    init();
    for (int i = 1; i <= n; i++) {
        l_dp[i] = query(0, arr[i] - 1) + 1;
        update(arr[i], l_dp[i]);
    }

    init();
    for (int i = n; i >= 1; i--) {
        r_dp[i] = query(max(arr[i] - x + 1, 1), MAX_ARR);
        update(arr[i], query(arr[i] + 1, MAX_ARR) + 1);
    }

    // for (int i = 1; i <= n; i++) {
    //     cout << i << ": " << l_dp[i] << " " << r_dp[i] << endl;
    // }

    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, l_dp[i] + r_dp[i]);
    cout << ans << '\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: 0 / 25