Submission #526813

#	Time	Username	Problem	Language	Result	Execution time	Memory
526813		hoanghq2004	Global Warming (CEOI18_glo)	C++14	100 / 100	116 ms	7048 KiB

glo

#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

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

const int N = 2e5 + 10;

int n, x;
int a[N], b[N];
int BIT[N], prf[N], suf[N];

void add(int i, int val) {
    for (; i < N; i += i & (- i)) BIT[i] = max(BIT[i], val);
}

int get(int i) {
    int ans = 0;
    for (; i; i -= i & - i) ans = max(ans, BIT[i]);
    return ans;
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> x;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    vector <int> dta;
    for (int i = 1; i <= n; ++i) dta.push_back(a[i]);
    sort(dta.begin(), dta.end());
    for (int i = 1; i <= n; ++i) b[i] = lower_bound(dta.begin(), dta.end(), a[i]) - dta.begin() + 1;
    for (int i = 1; i <= n; ++i) {
        prf[i] = get(b[i] - 1) + 1;
        add(b[i], prf[i]);
    }
    memset(BIT, 0, sizeof(BIT));
    for (int i = n; i >= 1; --i) {
        suf[i] = get(n - b[i]) + 1;
        add(n - b[i] + 1, suf[i]);
    }
    memset(BIT, 0, sizeof(BIT));
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        int newv = lower_bound(dta.begin(), dta.end(), a[i] + x) - dta.begin() + 1;
        ans = max(ans, get(newv - 1) + suf[i]);
        add(b[i], prf[i]);
    }
    cout << ans;
}

Compilation message (stderr)

glo.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
glo.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

• 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