제출 #1257362

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257362		sitingfake	Global Warming (CEOI18_glo)	C++20	100 / 100	85 ms	5128 KiB

glo

#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FOD(i, a, b) for(int i = a; i >= b; i--)
#define ALL(x) (x).begin(), (x).end()
#define file(name) if(fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define el cout << '\n'
#define maxn int(2e5 + 5)

using namespace std;

int n, x, res, a[maxn], id[maxn], t[maxn], l[maxn], r[maxn];

vector<int> V;

void update(int x, int v, bool type) {
    if(type) for(; x; x -= x & -x) t[x] = max(t[x], v);
    else     for(; x <= n; x += x & -x) t[x] = max(t[x], v);
}

int get(int x, bool type) {
    int res = 0;
    if(type) for(; x <= n; x += x & -x) res = max(res, t[x]);
    else     for(; x; x -= x & -x) res = max(res, t[x]);
    return res;
}

void compress() {
    FOR(i, 1, n) V.push_back(a[i]);
    sort(ALL(V));
    V.resize(unique(ALL(V)) - V.begin());
    FOR(i, 1, n) id[i] = lower_bound(ALL(V), a[i]) - V.begin() + 1;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> x;
    FOR(i, 1, n) cin >> a[i];
    compress();
    FOR(i, 1, n) {
        l[i] = get(id[i] - 1, 0) + 1;
        res = max(res, l[i]);
        update(id[i], l[i], 0);
    }
    memset(t, 0, sizeof t);
    FOD(i, n, 1) {
        r[i] = get(id[i] + 1, 1) + 1;
        update(id[i], r[i], 1);
    }
    memset(t, 0, sizeof t);
    FOD(i, n - 1, 1) {
        update(id[i + 1], r[i + 1], 1);
        int pos = upper_bound(ALL(V), a[i] - x) - V.begin() + 1;
        res = max(res, l[i] + get(pos, 1));
    }
    cout << res;
    return 0;
}

• 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