제출 #1272900

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272900		lucsdei10	Global Warming (CEOI18_glo)	C++20	100 / 100	243 ms	16524 KiB

glo

#include <bits/stdc++.h>
// #include <iostream>
// #include <vector>
// #include <cmath>
// #include <array>
// #include <algorithm>
#define int long long
const int MAXN = 1e6;
const long long inf = 1e10;
const int MAXS = 1e6;
const int mod = 1e9 + 7;
const int zero = 0;
using namespace std;
set<array<int, 2>> s;
void insert_(int x, int sz){
    s.insert({x, sz});
    auto it = s.find({x, sz});
    auto it2 = s.find({x, sz});
    if(it != s.begin()){
        it--;
        auto a = *it;
        auto b = *it2;
        if(a[1] >= b[1]){
            s.erase(it2);
            return;
        }
        else if(a[0] == b[0]){
            s.erase(it);
        }
    }
    it = s.find({x, sz});
    it2 = it;
    it2++;
    auto a = *it;
    auto b = *it2;
    while(it2 != s.end() && a[1] > b[1]){
        s.erase(it2);
        it = s.find({x, sz});
        it2 = it;
        it2++;
        if(it2 == s.end()) break;
        a = *it;
        b = *it2;
    }
}
int find(int x){
    array<int, 2> val = {x, inf};
    auto it = s.lower_bound(val);
    if(it == s.end()){
        it--;
    }
    auto arr = *it;
    if(arr[0] > x){
        it--;
        arr = *it;
        // if(x == 11) cout << arr[0] << '\n';
    }
    return arr[1];
}
int32_t main() {
    // freopen("moocast.in", "r", stdin);
    // freopen("moocast.out", "w", stdout);
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int t;
    // cin >> t;
    t = 1;
    while(t--){
        int n, x;
        cin >> n >> x;
        int a[n+1], lispref[n+1], lissuff[n+1];
        array<int, 2> dp[n+1];
        int ans = 0;
        stack<int> st;
        insert_(0, 0);
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            int sz = find(a[i]-1+x);
            // cout << sz << " " << a[i] << " " << a[i]-1+x << '\n';
            lispref[i] = sz;
            insert_(a[i], find(a[i]-1)+1);
            // for(auto el : s){
            //     cout << el[0] << " " << el[1] << '\n';
            // }
            // cout << '\n';
        }
        // reverse(a + 1, a + n + 1);
        while(!s.empty()){
            s.erase(s.begin());
        }
        insert_(-inf, 0);
        for(int i = n; i >= 1; i--){
            int sz = find(-a[i]-1) + 1;
            ans = max(ans, sz + lispref[i]);
            insert_(-a[i], sz);
        }
        cout << ans << "\n";
    }
}

• 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