Submission #612252

#	Time	Username	Problem	Language	Result	Execution time	Memory
612252		Andyvanh1	Global Warming (CEOI18_glo)	C++14	100 / 100	167 ms	16368 KiB

glo

#include <bits/stdc++.h>

using namespace std;

#define vt vector
#define pb push_back
#define all(x) x.begin(),x.end()
#define FORR1(x) for(int i = 0; i < (x); i++)
#define FORR2(j,x) for(int (j) = 0; (j) < (x); (j)++)
#define f first
#define s second

typedef vt<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

map<int,vi> mp;
map<int,int> dic;
int pp[10005];
int sz[10005];
int cst[10005];
int ans[10005][103];


int find(int x){
    return (x==pp[x] ? x : pp[x] = find(pp[x]));
}

void join(int a, int b){
    if(find(a)==find(b))return;
    int u = find(a), v = find(b);
    if(sz[u]>sz[v])swap(u,v);
    pp[u] = v;
    sz[v]+=sz[u];
}

int arr[200005];
int in2[200005];
int out2[200005];
int in1[200005];
int out1[200005];

void solve(){
    int n, x;
    cin>>n>>x;
    FORR1(n)cin>>arr[i];
    set<int,greater<>> st2;
    for(int i = n-1; i>=0; i--){
        auto it = st2.lower_bound(arr[i]);
        if(it == st2.end()){
            in2[i] = arr[i];
            out2[i] = -1;
            st2.insert(arr[i]);
        }else{
            in2[i] = arr[i];
            out2[i] = *it;
            st2.erase(it);
            st2.insert(arr[i]);
        }
    }
    set<int> st1;
    FORR1(n){
        auto it = st1.lower_bound(arr[i]);
        if(it == st1.end()){
            in1[i] = arr[i];
            out1[i] = -1;
            st1.insert(arr[i]);
        }else{
            in1[i] = arr[i];
            out1[i] = *it;
            st1.erase(it);
            st1.insert(arr[i]);
        }
    }
    int a = st1.size(), b = st2.size();
    vi cal1(a), cal2(b);
    FORR1(a)cal1[i] = -1;
    int att = 0;
    for(auto & e: st2){
        cal2[att] = e;
        att++;
    }
    int ans = b;
    int at1 = -1, at2 = b-1;
    FORR1(n){
        int l = 0, r = a;
        while(l!=r){
            int mid = (l+r)>>1;
            if(cal1[mid]==-1||(out1[i]!=-1&&out1[i]<cal1[mid])){
                r = mid;
            }else if(cal1[mid]==out1[i]){
                l = mid;
                r = mid;
            }else{
                l = mid+1;
            }
        }
        cal1[l] = in1[i];
        l = 0; r = b;
        while(l!=r){
            int mid = (l+r)>>1;
            if(cal2[mid]>in2[i]){
                l = mid+1;
            }else if(cal2[mid]<in2[i]){
                r = mid;
            }else{
                l = r = mid;
            }

        }
        cal2[l] = out2[i];
        if(cal2[at2]==-1){
            at2--;
        }
        if(at1==-1){

            if(cal1[0]-cal2[at2]<x){
                at1 = 0;
            }
        }else if(at2!=-1){

            if(cal1[at1]-cal2[at2]<x){
                if(at1!=a-1&&cal1[at1+1]!=-1&&cal1[at1+1]-cal2[at2]<x){
                    at1++;
                }
            }else{
                at2--;
                if(at2!=-1&&at1!=a-1&&cal1[at1+1]!=-1&&cal1[at1+1]-cal2[at2]<x){
                    at1++;
                }
            }
        }
        ans = max(ans, at1+at2+2);
        /*if(at1+at2+2==6){
            cout<<i<<'\n';
            cout<<at1<<' '<<at2<<'\n';
        }*/
    }
    ans = max(ans,(int)st1.size());
    cout<<ans<<'\n';


}


int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

• 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