제출 #1127744

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127744		Haciyev12	Global Warming (CEOI18_glo)	C++20	10 / 100	128 ms	9812 KiB

glo

  /***********************************
██╗░░██╗████████╗██╗░░░░░███╗░░░███╗
██║░░██║╚══██╔══╝██║░░░░░████╗░████║
███████║░░░██║░░░██║░░░░░██╔████╔██║
██╔══██║░░░██║░░░██║░░░░░██║╚██╔╝██║
██║░░██║░░░██║░░░███████╗██║░╚═╝░██║
╚═╝░░╚═╝░░░╚═╝░░░╚══════╝╚═╝░░░░░╚═╝
***********************************/

//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <unistd.h>

//#include "functions.h"

#define int l
#define f first
#define s second
#define endl '\n'
#define l long long
#define ara <<" "<<
#define pb push_back
#define pairs pair<l,l>
#define NO cout<<"NO"<<endl
#define stop system("pause")
#define YES cout<<"YES"<<endl
#define all(v) v.begin(),v.end()
#define yesno(v) ((v) ? "YES" : "NO")
#define dbg(x) cout<<#x<<" = "<<x<<endl;
#define filereader() ifstream cin(input);
#define fileprinter() ofstream cout(output);
#define fast ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);


using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less_equal<int> , rb_tree_tag, tree_order_statistics_node_update> indexed_set;

const l N = 2e5 + 5;
const l INF = 1e18;
const l mod = 1e9 + 7;

const string  input =  "input.txt";
const string output = "output.txt";

l gcd(l a, l b){
    if(b == 0){
        return a;
    }
    return gcd(b,a%b);
}

l binpow(l a, l b) {
    if (b == 0)
        return 1;

    l res = binpow(a, b / 2);

    if (b % 2)
        return ((res * res) % mod * a) % mod;
    else
        return (res * res) % mod;
}



void solve() {
    l n, x;
    cin >> n >> x;

    vector<l> v(n);
    vector<l> used(n, 0), par(n, 0);
    set<l> s;

    for (l &i : v) {
        cin >> i;
    }

    s.insert(v[n - 1]);
    for (l i = n - 2; i >= 0; i--) {
        if (!s.empty()) {
            l bg = *s.begin();
            if (v[i] < bg) {
                used[i] = 1;
                s.insert(v[i]);
            } else {
                auto t = s.upper_bound(v[i]);
                if (t != s.begin()) {
                    t--;
                    par[i] = *t;
                    s.erase(t);
                    s.insert(v[i]);
                }
            }
        }
    }

    l maks = s.size();
    set<l> st;

    for (l i = 0; i < n; i++) {
        if (!s.empty() && s.find(v[i]) != s.end()) {
            s.erase(v[i]);
        }

        if (used[i] == 0) {
            s.insert(par[i]);
        }

        l lst = -INF;
        if (!st.empty()) {
            lst = *st.rbegin();
        }

        v[i] -= x;

        if (v[i] <= lst && st.find(v[i]) != st.end()) {
            st.erase(st.lower_bound(v[i]));
        }
        st.insert(v[i]);

        while (!st.empty() && !s.empty() && *st.rbegin() >= *s.begin()) {
            auto p = st.end();
            p--;
            st.erase(p);
        }

        l sz = st.size() + s.size();
        maks = max(maks, sz);
    }

    cout << maks << endl;
}


signed main(){
    //fast;

    l n = 1;
    //cin>>n;

    while(n--){
        solve();
    }

}

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