제출 #1370659

#제출 시각아이디문제언어결과실행 시간메모리
1370659Ekber_EkberGlobal Warming (CEOI18_glo)C++20
100 / 100
213 ms23900 KiB
#include <bits/stdc++.h>
// #ifndef ONLINE_JUDGE
//     #include <debug.h>
// #else
//     #define debug(...)
// #endif
#define GOOD_LUCK ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;

constexpr int MAX = 2e+5 + 1, INF = 2e+16, MOD = 1e+9 + 7, K = 31;

struct BIT{
    int n;
    vector <int> t;
    void init(int n1) {
        n = n1;
        t.assign(n+2, 0);
    }
    int get(int r) {
        int res=0;
        while (r > 0) {
            res = max(res, t[r]);
            r -= (r & (-r));
        }
        return res;
    }
    void upd(int i, int x) {
        while (i <= n) {
            t[i] = max(t[i], x);
            i += (i & (-i));
        }
    }
};

int compress(vector <int> &v, int s = 1) {
    if (v.empty()) {
        return 0;
    }
    vector <int> v1 = v;
    sort(all(v1));
    v1.erase(unique(all(v1)), v1.end());
    int mx = s;
    for (int &i : v) {
        int k = lower_bound(all(v1), i) - v1.begin() + s;
        i = k;
        mx = max(mx, k);
    }
    return mx;
}

void _() {
    int n, x;
    cin >> n >> x;
    vector <int> v(n);
    for (int &i : v) cin >> i;
    vector <int> v1 = v;
    for (int &i : v) v1.pb(i + x);
    for (int &i : v) v1.pb(i - 1);
    for (int &i : v) v1.pb(i + x - 1);
    int mx = compress(v1);
    vector <array <int, 2>> dp(n, {1, 1});
    BIT t, t1;
    t.init(mx);
    t.upd(v1[0], 1);
    t1.init(mx);
    t1.upd(v1[n], 1);
    for (int i = 1; i < n; i++) {
        dp[i][0] = max(1LL, t.get(v1[i + 2 * n]) + 1);
        dp[i][1] = max({1LL, t.get(v1[3 * n + i]) + 1, t1.get(v1[3 * n + i]) + 1});
        t.upd(v1[i], dp[i][0]);
        t1.upd(v1[i + n], dp[i][1]);
    }
    int res = 0;
    for (int i = 0; i < n; i++) res = max(res, max(dp[i][0], dp[i][1]));
    cout << res;
}

signed main() {

    GOOD_LUCK

    int tests=1;
    // cin >> tests;
    for (int i=1; i <= tests; i++) {
        _();
        cout << endl;
    }

    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…