Submission #972962

#	Time	Username	Problem	Language	Result	Execution time	Memory
972962		efedmrlr	Global Warming (CEOI18_glo)	C++17	75 / 100	545 ms	262144 KiB

glo

#include <bits/stdc++.h>

#define lli long long int
#define pb push_back
#define MP make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define ld long double

using namespace std;

const int N = 1e5 + 5;
const int INF = 1e9 + 500;
const int MX = 1e9 + 5;
void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

struct Node {
    
    Node *lc, *rc;
    int val;
    Node() : lc(NULL), rc(NULL), val(0) {}
    void extend() {
        if(!lc) lc = new Node();
        if(!rc) rc = new Node();
    }
    int query(int tl, int tr, int l, int r) {
        if(tl >= l && tr <= r) {
            return val;
        }
        if(tl > r || tr < l) return 0;
        int tm = (tl + tr) >> 1;
        extend();
        return max(lc->query(tl, tm, l, r), rc->query(tm + 1, tr, l, r));
    }
    void update(int tl, int tr, int ind, int nw) {
        if(tl == tr) {
            val = max(val, nw);
            return;
        }
        int tm = (tl + tr) >> 1;
        extend();
        if(ind <= tm) {
            lc->update(tl, tm, ind, nw);
        }
        else {
            rc->update(tm + 1, tr, ind, nw);
        }
        val = max(lc->val, rc->val);
    }
};


int n, x;
vector<int> t;
vector<int> pr, suf;
Node *seg;

void solve() {
    cin >> n >> x;
    t.assign(n + 1, 0);
    pr.resize(n + 3);
    suf.resize(n + 3);
    for(int i = 1; i <= n; i++) {
        cin >> t[i];
    }
    set<array<int, 2> > st;
    for(int i = 1; i <= n; i++) {
        auto itr = st.lower_bound({t[i], 0});
        if(itr == st.end()) {
            pr[i] = st.size() + 1;
        }
        else {
            pr[i] = (*itr)[1];
            st.erase(itr);
        }
        st.insert({t[i], pr[i]});
    }
    st.clear();
    for(int i = n; i >= 1; i--) {
        auto itr = st.lower_bound({-t[i], 0});
        if(itr == st.end()) {
            suf[i] = st.size() + 1;
        }
        else {
            suf[i] = (*itr)[1];
            st.erase(itr);
        }
        st.insert({-t[i], suf[i]});
    }
    st.clear();
    seg = new Node();
    int ans = 0;
    for(int i = n; i >= 1; i--) {
        int ret = pr[i];
        if(t[i] + 1 - x <= MX) {
            ret += seg->query(0, MX, max(0, t[i] + 1 - x), MX);
        }
        ans = max(ans, ret);
        seg->update(0, MX, t[i], suf[i]);
    }
    cout << ans << "\n";

}

signed main() {
    fastio();
    solve();
}

• 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: 0 / 25