Submission #931290

#	Time	Username	Problem	Language	Result	Execution time	Memory
931290		AtabayRajabli	Global Warming (CEOI18_glo)	C++17	100 / 100	49 ms	10372 KiB

glo

#include <bits/stdc++.h>

// author : a1abay

#define pb          push_back
#define all(v)      v.begin(), v.end()
#define int         ll
#define gcd(a, b)   __gcd(a, b)
#define lcm(a, b)   (a*b / (__gcd(a, b)))
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

typedef long long           ll;
const int inf =             1e9 + 7;
const int inff =            1e18 + 7;
const int sz =              2e5 + 5;
using namespace             std;

int n, x;
int a[sz];

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> x;
    for(int i = 0; i < n; i++)cin >> a[i];

    vector<int> dp(n + 5, inff);
    vector<int> l(n + 5, 0), r(n + 5, 0);
    for(int i = 0; i < n; i++)
    {
        int ind = lower_bound(all(dp), a[i]) - dp.begin();
        dp[ind] = a[i];
        l[i] = ind + 1;
    }

    int mx = 0;
    dp = vector<int>(n + 5, inff);
    for(int i = n - 1; i >= 0; i--)
    {
        int pos = lower_bound(all(dp), -(a[i] - x)) - dp.begin();
        int ind = lower_bound(all(dp), -a[i]) - dp.begin();
        dp[ind] = -a[i];
        mx = max(mx, l[i] + pos);
    }

    cout << mx;
}

• 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