Submission #1310078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310078		qrn	Global Warming (CEOI18_glo)	C++20	22 / 100	448 ms	39584 KiB

glo

#include "bits/stdc++.h"
using namespace std;
#define intt long long
#define fi first
#define se second
#define endl "\n"

const intt mxN = 2e5+67;
const intt LG = 20;
const intt inf = 1e18; 
const intt mod = 1e9 + 7;
const intt p = 997;

vector<intt> a(mxN), dpL(mxN), dpR(mxN), seg(4 * mxN), seg2(4*mxN);
map<intt,intt> comp;
set<intt> st;
intt avil = 1;

void update(intt node, intt l, intt r, intt pos, intt val, vector<intt> &seg) {
    if(l == r) {
        seg[node] = val;
        return;
    }
    intt mid = (l + r) / 2;
    if(pos <= mid) {
        update(node * 2, l, mid, pos, val, seg);
    } else {
        update(node * 2 + 1, mid + 1, r, pos, val, seg);
    }
    seg[node] = max(seg[node * 2], seg[node * 2 + 1]);
}


intt get(intt node, intt l, intt r, intt ql, intt qr, vector<intt> &seg) {
    if(ql > r || qr < l || ql > qr) return 0ll;
    if(ql <= l && r <= qr) {
        return seg[node];
    }
    intt mid = (l + r) / 2;
    return max(get(node * 2, l, mid, ql, qr, seg), get(node * 2 + 1, mid + 1, r, ql, qr, seg));
}

void smile() {
    intt n, k;
    cin >> n >> k;
    for(intt i = 0; i < n; i++) {
        cin >> a[i];
        st.insert(a[i]);
    }
    st.insert(k);
    for(auto u : st) {
        comp[u] = avil++;
    }
    k = comp[k];
    for(intt i = 0; i < n; i++) a[i] = comp[a[i]];

    dpL[0] = 1ll;
    update(1, 1, avil, a[0], dpL[0], seg);
    for(intt i = 1; i < n; i++) {
        intt g = get(1, 1, avil, 1, a[i]-1, seg);
        dpL[i] = (g + 1);
        update(1, 1, avil, a[i], dpL[i], seg);
    }

    seg.assign(4 * avil + 1, 0ll);
    dpR[n-1] = 1;
    update(1, 1, avil, a[n-1], 1ll, seg);
    update(1, 1, avil, a[n-1], 1ll, seg2);
    // for(intt i = 0; i < n; i++) cout << a[i] << " ";
    // cout << endl;
    for(intt i = n - 2; i >= 0; i--) {
        intt g = get(1, 1, avil, a[i]-k+1, avil, seg);
        intt g2 = get(1, 1, avil, a[i]+1, avil, seg2);
        dpR[i] = (g + 1);
        update(1, 1, avil, a[i], g2 + 1, seg);
        update(1, 1, avil, a[i], g2 + 1, seg2);
    }
    intt ans = 0;
    for(intt i = 0; i < n; i++) {
        // cout << i << ": " << dpL[i] << " " << dpR[i] << endl;
        ans = max(ans, dpL[i] + dpR[i] - 1);
    }
    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 
    cout.tie(NULL);

    // freopen("island.in", "r", stdin);
    // freopen("island.out", "w", stdout)

    intt t = 1, buu = 1;
    // cin >> t;
    while(t--){
        // cout << endl;
        // cout << "Case #" << buu++ << ": ";
        smile();
    }
}

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