Submission #889335

#	Time	Username	Problem	Language	Result	Execution time	Memory
889335		Perl32	Global Warming (CEOI18_glo)	C++14	10 / 100	130 ms	10948 KiB

glo

//I wrote this code 4 u <3
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

const ll INF = (ll) 1e18 + 1e9;

struct SegTree {
    vector<int> t;
    int sz;

    SegTree(int n) {
        sz = n;
        t.resize(sz << 1);
    }

    void upd(int i, int v) {
        i += sz;
        t[i] = v;
        i >>= 1;
        while (i) {
            t[i] = max(t[i << 1], t[i << 1 | 1]);
            i >>= 1;
        }
    }

    int get(int l, int r) {
        l += sz;
        r += sz;
        int ret = 0;
        while (l < r) {
            if (l & 1) ret = max(ret, t[l++]);
            if (r & 1) ret = max(ret, t[--r]);
            l >>= 1;
            r >>= 1;
        }
        return ret;
    }
};

signed main(int32_t argc, char *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, x;
    cin >> n >> x;
    vector<ll> a(n), srt;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        srt.push_back(a[i]);
        srt.push_back(a[i] - x);
    }
    sort(srt.begin(), srt.end());
    srt.resize(unique(srt.begin(), srt.end()) - srt.begin());
    SegTree st(srt.size());
    vector<ll> dp(n + 1, INF);
    dp[0] = -INF;
    int mx = 0;
    for (auto v : a) {
        int pos = lower_bound(srt.begin(), srt.end(), v) - srt.begin(), cnt = lower_bound(dp.begin(), dp.end(), v) - dp.begin();
        mx = max({mx, st.get(0, pos) + 1, cnt});
        st.upd(pos, cnt);
        dp[lower_bound(dp.begin(), dp.end(), v - x) - dp.begin()] = v - x;
    }
    cout << mx;
}

/*

 */

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