제출 #1284777

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284777		celes	Global Warming (CEOI18_glo)	C++20	100 / 100	92 ms	10008 KiB

glo

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

#define     ll long long
#define    pll pair<ll, ll>
#define    pii pair<int, int>
#define     fi first
#define     se second
#define     pb push_back
#define     all(v) (v).begin(), (v).end()
#define     Unique(v) sort(all(v)); (v).erase(unique(all(v)), (v).end())

const int N = 3e5 + 5;
const int INF = 3e5 + 2;

int n;
ll x;
ll a[N], c[N], val[N];
vector<ll> b;

struct Fenwick {
    ll bit[N];

    void update(int pos, ll val) {
        while (pos <= INF) {
            bit[pos] = max(bit[pos], val);
            pos += pos & -pos;
        }
    }

    ll get(int pos) {
        ll ans = 0;
        while (pos > 0) {
            ans = max(ans, bit[pos]);
            pos -= pos & -pos;
        }
        return ans;
    }
} fenpre, fensuf;

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

    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        c[i] = a[i];
        b.pb(a[i]);
    }

    // Nén toạ độ
    b.pb(0);
    Unique(b);
    for (int i = 1; i <= n; i++)
        a[i] = lower_bound(all(b), a[i]) - b.begin();

    // LIS từ trái sang
    for (int i = 1; i <= n; i++) {
        ll p = fenpre.get(a[i] - 1) + 1;
        val[i] = p;
        fenpre.update(a[i], p);
    }

    ll res = 0;

    // LIS từ phải sang và ghép
    for (int i = n; i >= 1; i--) {
        ll p = fensuf.get(INF - a[i] - 1) + 1;

        // vị trí của (a[i] - x)
        ll low = max(0ll, c[i] - x);
        int idx = upper_bound(all(b), low) - b.begin() - 1;

        res = max(res, val[i] + fensuf.get(INF - idx - 1));

        fensuf.update(INF - a[i], p);
    }

    cout << res;
}

• 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