제출 #1280185

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280185		hanguyendanghuy	Global Warming (CEOI18_glo)	C++20	100 / 100	92 ms	9988 KiB

glo

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
constexpr ll MAXN=3e5+5,MAXV=3e5,MOD=1e9+7,INF=3e5+2;
ll n,m,i,j,p,k,ans,dem,st,en,a[MAXN],b[MAXN],x,val[MAXN],c[MAXN];
struct fen{
    ll b[MAXN];
    ll get(ll pos){
        ll ans=0;
        if(pos==0) return 0;
        while(pos>0){
            ans=max(ans,b[pos]);
            pos-=pos&-pos;
        }
        return ans;
    }
    void update(ll pos,ll val){
        while(pos<=INF){
            b[pos]=max(b[pos],val);
            pos+=pos&-pos;
        }
    }
} fensuf,fenpre;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>x;
    vector<ll> b;
    for(i=1;i<=n;i++){
        cin>>a[i];
        c[i]=a[i];
        b.pb(a[i]);
    }
    b.pb(0);
    sort(b.begin(),b.end());
    b.resize(unique(b.begin(), b.end()) - b.begin());
    for(i=1;i<=n;i++)
        a[i]=lower_bound(b.begin(),b.end(),a[i])-b.begin();
    for(i=1;i<=n;i++){
        ll p=fenpre.get(a[i]-1)+1;
        val[i]=p;
        fenpre.update(a[i],p);
    }
    ll ans=0;
    for(i=n;i>=1;i--){
        ll p=fensuf.get(INF-a[i]-1)+1;
        c[i]=upper_bound(b.begin(),b.end(),max(0ll,c[i]-x))-b.begin()-1;
        ans=max(ans,val[i]+fensuf.get(INF-c[i]-1));
        fensuf.update(INF-a[i],p);
    }
    cout<<ans;
}

• 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