Submission #1166792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166792		ali2241	Global Warming (CEOI18_glo)	C++17	100 / 100	70 ms	4548 KiB

glo

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define arr2 array<int, 2>
#define arr3 array<int, 3>
#define popcount __builtin_popcount
#define ctz __builtin_ctz
#define ff first
#define ss second
//espertam
using namespace std;
using namespace __gnu_pbds;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rb3;

// const int M = 1e9 + 7, N = (1 << 20), L = (1 << 19);

// int seg[N];

// int get(int l, int r, int l1 = 0, int r1 = L, int ind = 1) {
//     if (l < r or r < l1 or l > r1) {
//         return 0;
//     }
//     int mid = (l1 + r1) / 2;
//     if (l1 == l and r1 == r) {
//         return ind;
//     }
//     return max(get(l, r, l1, mid, 2 * ind), get(l, r, mid + 1, r1, 2 * ind + 1));

// }

void fun() {
    int n, x;
    cin >> n >> x;
    int arr[n];
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    vector<int> lis;
    int dp[n];
    for (int i = 0; i < n; ++i) {
        int p = lower_bound(lis.begin(), lis.end(), arr[i]) - lis.begin();
        dp[i] = p + 1;
        if (p == lis.size()) {
            lis.push_back(arr[i]);
        }
        else {
            lis[p] = arr[i];
        }
    }
    int ans = 1;
    lis.clear();
    for (int i = n - 1; i >= 0; --i) {
        ans = max(ans, dp[i] + (lower_bound(lis.begin(), lis.end(), arr[i] - x, greater<int>()) - lis.begin()));
        int p = lower_bound(lis.begin(), lis.end(), arr[i], greater<int>()) - lis.begin();
        if (p == lis.size()) {
            lis.push_back(arr[i]);
        }
        else {
            lis[p] = arr[i];
        }
    }
    cout << ans << "\n";
}

int32_t main() {
    // ios::sync_with_stdio(0);
    // cout.tie(0);
    // cin.tie(0);
    // int tc;
    // cin >> tc;
    // while (tc--)
    fun();
}

• 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