Submission #1260370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260370		pasta	Global Warming (CEOI18_glo)	C++20	48 / 100	42 ms	1860 KiB

glo

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, ll> pii;


#define pb		push_back
#define all(x)	x.begin(), x.end()
// #define int ll
#define fast_io     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define lc          (id * 2)
#define rc          (lc + 1)
#define F           first
const int inf = 1e9 + 10;
const int maxn = 1e5 + 10;
const int mod = 19 + 7;;

int n, x, a[maxn], dp[maxn], mn[maxn], mx[maxn];

int calc_l(int i) {
    int l = 1, r = maxn;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        if (mn[mid - 1] < a[i])
            l = mid;
        else
            r = mid;
    }
    dp[i] = l;
	mn[l] = min(a[i], mn[l]);
    return l;
}

void calc_r(int i) {
    int l = 1, r = maxn;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        if (mx[mid - 1] > a[i])
            l = mid;
        else
            r = mid;
    }
    mx[l] = max(a[i], mx[l]);
}

signed main() {
    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < maxn; i++) {
        mn[i] = inf;
        mx[i] = -inf;
    }

    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, calc_l(i));
    
    // cout << ans << '\n';
    for (int i = n; i > 1; i--) {
        calc_r(i);
        int l = 0, r = maxn;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (mx[mid] > a[i - 1] - x) {
                l = mid;
            }
            else {
                r = mid;
            }
        }
        ans = max(ans, dp[i - 1] + l);
    }

    cout << ans << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 0 / 10
• Subtask 5: 20 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25