제출 #1260634

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1260634		nguyenvu	Railway (BOI17_railway)	C++17	0 / 100	59 ms	7880 KiB

railway

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,x;
ll a[200005],st[4*200005],s[200005],si[200005],dp[200005];
set<int> v;
vector<int> f;

void update(int id,int l,int r,int i,int val){
    if(l>i || r<i) return;
    if(l==r){
        st[id]=val;
        return;
    }
    int mid=(l+r)>>1;
    update(id*2,l,mid,i,val);
    update(id*2+1,mid+1,r,i,val);
    st[id]=max(st[id*2],st[id*2+1]);
}

ll get(int id,int l,int r,int u,int v){
    if(l>v || r<u) return -2e9;
    if(l>=u && r<=v) return st[id];

    int mid=(l+r)>>1;
    return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}

int main(){
    ll x;
    cin>>n>>x;
    v.insert(-1000);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        dp[i]=2e9;
        v.insert(a[i]);
    }
    for(int i:v) f.push_back(i);
    for(int i=1;i<=n;i++){
        int k=lower_bound(dp+1,dp+n+1,a[i])-dp;
        dp[k]=a[i];
        s[i]=k;
    }
    memset(dp,2e9,sizeof(dp));
    for(int i=n;i>=1;i--){
        int k=lower_bound(dp+1,dp+n+1,-a[i])-dp;
        dp[k]=-a[i];
        si[i]=k;
    }
    f.push_back(2e9);
    ll ans=0;
    for(int i=1;i<=n;i++){
        int k=lower_bound(f.begin(),f.end(),a[i])-f.begin();
        update(1,1,n,k,s[i]);
        k=lower_bound(f.begin(),f.end(),a[i+1]+x)-f.begin();
        k--;
        ans=max(ans,si[i+1]+get(1,1,n,1,k));
    }
    cout<<ans;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 0 / 7
• Subtask 4: 0 / 29
• Subtask 5: 0 / 16
• Subtask 6: 0 / 25