Submission #1308087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308087		Owstin	Global Warming (CEOI18_glo)	C++20	62 / 100	196 ms	10644 KiB

glo

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define FAST_IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define pb push_back
#define all(x) begin(x), end(x)
#define umap unordered_map
#define space " "
#define TEST_CASES int a; cin >> a; for (int i = 0; i < a; i++) {solve(); cout << endl;}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template <class T> class SegmentTree {
private:
    /* CHANGE DEPENDING ON TYPE OF SEG TREE */
    const T DEFAULT = 0;
    int len;
    vector<T> segtree;
    /* CHANGE DEPENDING ON TYPE OF SEG TREE */
    T combine(const T &a, const T &b) { return max(a, b); }
    void build(const vector<T> &arr, int at, int at_left, int at_right) {
        if (at_left == at_right) {
            segtree[at] = arr[at_left];
            return;
        }
        int mid = (at_left + at_right) / 2;
        build(arr, 2 * at, at_left, mid);
        build(arr, 2 * at + 1, mid + 1, at_right);
        segtree[at] = combine(segtree[2 * at], segtree[2 * at + 1]);
    }
    void set(int ind, T val, int at, int at_left, int at_right) {
        if (at_left == at_right) {
            segtree[at] = val;
            return;
        }
        int mid = (at_left + at_right) / 2;
        if (ind <= mid) {
            set(ind, val, 2 * at, at_left, mid);
        } else {
            set(ind, val, 2 * at + 1, mid + 1, at_right);
        }
        segtree[at] = combine(segtree[2 * at], segtree[2 * at + 1]);
    }
    T range(int start, int end, int at, int at_left, int at_right) {
        if (at_right < start || end < at_left) { return DEFAULT; }
        if (start <= at_left && at_right <= end) { return segtree[at]; }
        int mid = (at_left + at_right) / 2;
        T left_res = range(start, end, 2 * at, at_left, mid);
        T right_res = range(start, end, 2 * at + 1, mid + 1, at_right);
        return combine(left_res, right_res);
    }
public:
    SegmentTree(int len) : len(len) { segtree = vector<T>(len * 4, DEFAULT); };
    SegmentTree(const vector<T> &arr) : len(arr.size()) {
        segtree = vector<T>(len * 4, DEFAULT);
        build(arr, 1, 0, len - 1);
    }
    void set(int ind, T val) { set(ind, val, 1, 0, len - 1); }
    T range(int start, int end) { return range(start, end, 1, 0, len - 1); }
};

void solve() {
    int n, x; cin >> n >> x;
    vector<int> vec(n);
    for (int i = 0; i < n; i++) {
        cin >> vec[i];
    }
    vector<int> vect = vec;
    sort(all(vect));
    vect.erase(unique(all(vect)), vect.end());
    for (int i = 0; i < n; i++) {
        vec[i] = lower_bound(all(vect), vec[i]) - vect.begin();
    }
    int uni = vect.size();
    vector<int> add(uni);
    for (int i = 0; i < uni; i++) {
        add[i] = upper_bound(all(vect), vect[i] - x) - vect.begin();
    }
    SegmentTree<int> stree(uni + 1);
    vector<pair<int, int>> pref(n);
    vector<int> pdp;
    for (int i = 0; i < n; i++) {
        auto it = lower_bound(all(pdp), vec[i]);
        if (it == pdp.end()) {
            pdp.pb(vec[i]);
        }
        else {
            *it = vec[i];
        }
        pref[i] = {pdp.size(), pdp.back()};
    }
    int res = pref.back().first;
    SegmentTree<int> sdp(uni + 1);
    for (int i = n - 1; i > 0; i--) {
        sdp.set(vec[i], stree.range(vec[i] + 1, uni) + 1);
        stree.set(vec[i], sdp.range(vec[i], vec[i]));
        res = max(res, pref[i - 1].first + stree.range(add[pref[i - 1].second], uni));
    }
    cout << res;
}

int main() {
    FAST_IO;
    //freopen("pcb.in", "r", stdin);
    //freopen("pcb.out", "w", stdout);
    //TEST_CASES;
    solve(); cout << endl;
    /*int a; cin >> a;
    for (int i = 1; i <= a; i++){
        cout << "Case #" << i << ": ";
        solve();
        cout << endl;
    }*/
}

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