Submission #1137983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137983		trinhvtuan	Global Warming (CEOI18_glo)	C++20	100 / 100	347 ms	17816 KiB

glo

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define li pair<ll,int>
using namespace std;
int n;
li a[400003],b[400003];
ll x;
vector<ll> nen;
int st[1600003],lmx[400003],rmx[400003];
int lay(int x){
    return lower_bound(nen.begin(),nen.end(),x)-nen.begin()+1;
}
void update(int id,int l,int r,int i,int x){
    if (i<l||r<i) return;
    if (l==r){
        st[id]=max(st[id],x);
        return;
    }
    int mid=(l+r)/2;
    update(id*2,l,mid,i,x);
    update(id*2+1,mid+1,r,i,x);
    st[id]=max(st[id*2],st[id*2+1]);
}
int get(int id,int l,int r,int u,int v){
    if (v<l||r<u) return 0;
    if (u<=l&&r<=v) {
        return st[id];
    }
    int mid=(l+r)/2;
    return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>x;
    for (int i=1;i<=n;i++) {
        cin>>a[i].fi;
        a[i].se=b[i].se=i;
    }
    for (int i=1;i<=n;i++){
        nen.push_back(a[i].fi);
        nen.push_back(x+a[i].fi);
    }
    sort(nen.begin(),nen.end());
    nen.erase(unique(nen.begin(),nen.end()),nen.end());
    int m=nen.size();
    for (int i=0;i<=m*4;i++) st[i]=0;
    for (int i=1;i<=n;i++){
        b[i].fi=lay(a[i].fi+x);
        a[i].fi=lay(a[i].fi);
    }
    for (int i=1;i<=n;i++) {
        int sz=(a[i].fi>1)?get(1,1,m,1,a[i].fi-1):0;
        lmx[a[i].se]=sz+1;
        update(1,1,m,a[i].fi,sz+1);
    }

    for (int i=0;i<=m*4;i++) st[i]=0;
    for (int i=n;i>0;i--){
        int sz=(b[i].fi+1<=m)?get(1,1,m,b[i].fi+1,m):0;
        rmx[b[i].se]=sz+1;
        update(1,1,m,b[i].fi,sz+1);
    }
    for (int i=0;i<=m*4;i++) st[i]=0;
    int kq=1;
    for (int i=1;i<=n;i++){
        int sz=get(1,1,m,1,b[i].fi-1);
        kq=max(kq,sz+rmx[i]);
        update(1,1,m,a[i].fi,lmx[i]);
    }
    cout<<kq;
    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