제출 #1166924

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166924		raul2008487	Global Warming (CEOI18_glo)	C++20	100 / 100	1895 ms	159472 KiB

glo

#include <bits/stdc++.h>
#define ll int
#define pll pair<ll,ll>
#define pb push_back
#define eb emplace_back
#define vl vector<ll>
#define fi first
#define se second
#define in insert
#define mpr make_pair
#define lg(x) __lg(x)
#define bpc(x) __builtin_popcount(x)
#define all(v) v.begin(), v.end()
#define endl '\n'
using namespace std;
const int sz = 2e5 + 5;
const int mod = 998244353;
ll inf = 1e8;
ll dp[sz];
struct BIT{
    vl ft;
    ll n;
    void init(ll N){
        n = N + 10;
        ft.assign(n + 5, 0);
    }
    void add(ll pos, ll val){
        for(pos; pos <= n; pos += (pos & (-pos))){
            ft[pos] = max(ft[pos], val);
        }
    }
    ll get(ll pos){
        ll ans = 0;
        for(pos; pos > 0; pos -= (pos & (-pos))){
            ans = max(ans, ft[pos]);
        }
        return ans;
    }
};
struct BT{
    vector<multiset<ll>> ft;
    ll n;
    void init(ll N){
        n = N + 10; 
        multiset<ll> empt;
        empt.in(0);
        for(int i = 1; i <= (n + 5); i++){
            ft.pb(empt);
        }
    }
    void add(ll pos, ll val){
        for(pos; pos <= n; pos += (pos & (-pos))){
            ft[pos].in(val);
            // cout << "+ "<< pos << ' '  << val << endl;
        }
        // cout << endl;
    }
    void rem(ll pos, ll val){
        for(pos; pos <= n; pos += (pos & (-pos))){
            ft[pos].erase(ft[pos].find(val));
            // cout << "- "<< pos << ' '  << val << endl;
        }
    }
    ll get(ll pos){
        ll ans = 0;
        for(pos; pos > 0; pos -= (pos & (-pos))){
            ll mx = *(--ft[pos].end());
            ans = max(ans, mx);
        }
        return ans;
    }
};
void _()
{
    BT suf;
    ll n, x, i, j, c = 0, ans = 0;
    cin >> n >> x;
    suf.init(2 * n);
    vl v(n + 1), p(n + 1), cm;
    for(i = 1; i <= n; i++){
        cin >> v[i];
        cm.pb(v[i]);
        cm.pb(v[i] - x);
    }   
    map<ll, ll> cmp;
    sort(all(cm));
    for(auto k: cm){
        if(!cmp[k]){
            cmp[k] = (++c);
        }
    }
    ll mx = (2 * n + 1);
    // cout << mx << ' ' << cmp[v[n]] << endl;
    for(i = n; i > 0; i--){
        // cerr << i << endl;
        p[i] = cmp[v[i] - x];
        v[i] = cmp[v[i]];
        ll pos = (mx - v[i]);
        ll to = suf.get(pos - 1), new_val = to + 1;
        dp[i] = new_val;
        suf.add(pos, new_val);
        // cout << "+ " << pos << ' ' << new_val << endl;
    }
    // cerr << "#" << endl;
    BIT pref;
    pref.init(2 * n);
    for(i = 1; i <= n; i++){
        ll from = pref.get(p[i] - 1);
        pref.add(p[i], from + 1);
        ll pos = (mx - v[i]);
        // cerr << pos << endl;
        suf.rem(pos, dp[i]);
        // cout << "- " << pos << ' ' << dp[i] << endl;
        ll to = suf.get((mx - p[i]) - 1);
        ans = max(ans, from + to + 1);
    }
    cout << ans << endl;
    // for(i = 1; i <= n; i++){
    //     cout << dp[i] << ' ';
    // }cout << endl;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) _();
}
/*
8 10
7 3 5 12 2 7 3 4
*/

• 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