Submission #972972

#	Time	Username	Problem	Language	Result	Execution time	Memory
972972		efedmrlr	Global Warming (CEOI18_glo)	C++17	100 / 100	136 ms	9312 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);
}

int n, x;
vector<int> t;
vector<int> pr, suf;

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();
    int ans = 0;
    st.insert({INF, 0});
    for(int i = n; i >= 1; i--) {
        int ret = pr[i];
        if(t[i] + 1 - x <= MX) {
            ret += (*st.lower_bound({t[i] + 1 - x, 0}))[1];
        }
        ans = max(ans, ret);
        auto itr = st.upper_bound({t[i], suf[i]});
        if(itr != st.end() && (*itr)[1] >= suf[i]) {
            continue;
        }
        while(itr != st.begin()) {
            itr--;
            if((*itr)[1] > suf[i]) {
                break;
            }
            else {
                itr = st.erase(itr);
            }
        }
        st.insert({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: 25 / 25