Submission #1098688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098688		ortsac	Lottery (CEOI18_lot)	C++17	0 / 100	6 ms	3928 KiB

lot

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 10;

int n, x;

struct SegTree {
    int seg[4*MAXN];

    void build() {
        memset(seg, 0, sizeof seg);
    }

    void update(int node, int l, int r, int po, int val) {
        if (l == r) {
            seg[node] = max(seg[node], val);
            return;
        }
        int m = (l+r)/2;
        if (po <= m) update(2*node, l, m, po, val);
        else update(2*node + 1, m + 1, r, po, val);
        seg[node] = max(seg[2*node], seg[2*node + 1]);
    }

    int query(int node, int l, int r, int tl, int tr) {
        if (r < l) return 0;
        if ((r < tl) || (tr < l)) return 0;
        if ((tl <= l) && (r <= tr)) return seg[node];
        int m = (l+r)/2;
        return max(query(2*node, l, m, tl, tr), query(2*node + 1, m + 1, r, tl, tr));
    }
};

int32_t main() {
    cin >> n >> x;
    vector<int> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    vector<int> ord = v;
    sort(ord.begin(), ord.end());
    ord.erase(unique(ord.begin(), ord.end()), ord.end());
    map<int, int> re;
    for (int i = 0; i < ((int)ord.size()); i++) re[ord[i]] = i;
    // calc prefix
    SegTree seg;
    seg.build();
    vector<int> pf(n);
    for (int i = 0; i < n; i++) {
        // calcular pf[i]
        // posso pegar até v[i]+x
        auto it = lower_bound(ord.begin(), ord.end(), v[i] + x);
        int mxPo = (it - ord.begin() - 1);
        //cout << "this is mxpo: " << mxPo << "\n";
        pf[i] = seg.query(1, 0, n - 1, 0, mxPo);
        // atualizar aqui
        int po = re[v[i]];
        int mx = seg.query(1, 0, n - 1, 0, po - 1);
        //cout << mx << "\n";
        seg.update(1, 0, n - 1, po, mx + 1);
    }
    seg.build();
    int ans = 0;
    for (int i = n - 1; i >= 0; i--) {
        // atualizar aqui
        int po = re[v[i]];
        int mx = seg.query(1, 0, n - 1, po + 1, n - 1);
        seg.update(1, 0, n - 1, po, mx + 1);
        ans = max(ans, mx + 1 + pf[i]);
        //cout << i << " " << mx << " " << pf[i] << "\n";
    }
    cout << ans << "\n";
}

• Subtask 1: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20