Submission #1132556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132556		lopkus	Global Warming (CEOI18_glo)	C++20	100 / 100	474 ms	54920 KiB

glo

#include <bits/stdc++.h>
using namespace std;
const int N=2e6+5;
const long long MAXN=1e9+7;
int n;
int d;
vector<int>a(N);
vector<int>F(N);
struct implicit{
    int idxx=1;
    int t[4*N];
    int ll[4*N];
    int rr[4*N];
    void update(int node,int tl,int tr,int index,int value){
        if(tl==tr){
            t[node]=value;
            return;
        }
        int tm=(tl+tr)/2;
        if(index<=tm){
            if(!ll[node])ll[node]=++idxx;
            update(ll[node],tl,tm,index,value);
        }
        else{
            if(!rr[node])rr[node]=++idxx;
            update(rr[node],tm+1,tr,index,value);
        }
        t[node]=max((ll[node]?t[ll[node]]:0),(rr[node]?t[rr[node]]:0));
    }
    void update(int i,int v){update(1,1,MAXN,i,v);}
    int query(int node,int tl,int tr,int l,int r){
        if(tl>=l&&tr<=r)return t[node];
        int tm=(tl+tr)/2;
        int ans=0;
        if(ll[node]&&l<=tm)ans=query(ll[node],tl,tm,l,r);
        if(rr[node]&&tm<r)ans=max(ans,query(rr[node],tm+1,tr,l,r));
        return ans;
    }
    int query(int l,int r){return query(1,1,MAXN,l,r);}
}seg;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>d;
    for(int i=1;i<=n;i++)cin>>a[i];
    F=a;
    vector<int>kompres;
    for(int i=1;i<=n;i++)kompres.push_back(a[i]);
    sort(kompres.begin(),kompres.end());
    for(int i=1;i<=n;i++)a[i]=lower_bound(kompres.begin(),kompres.end(),a[i])-kompres.begin()+1;
    int lis[n+1];
    for(int i=0;i<=n;i++)lis[i]=1;
    for(int i=1;i<=n;i++){
        lis[i]=seg.query(0,a[i]-1)+1;
        seg.update(a[i],lis[i]);
    }
    for(int i=1;i<=n;i++)seg.update(a[i],0);
    int suflis[n+1];
    for(int i=0;i<=n;i++)suflis[i]=1;
    for(int i=n;i>=1;i--){
        suflis[i]=seg.query(a[i]+1,n)+1;
        seg.update(a[i],suflis[i]);
    }
    int ans=0;
    for(int i=1;i<=n;i++)ans=max(ans,suflis[i]);
    for(int i=1;i<=n;i++)seg.update(a[i],0);
    /*
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(abs(F[i]-F[j])<d){
                ans=max(ans,lis[i]+suflis[j]);
            }
        }
    }*/
    if(!d){
        cout<<ans;
        return 0;
    }
    d--;
    for(int i=n;i>=1;i--){
        ans=max(ans,lis[i]+seg.query(F[i]-d,F[i]));
        ans=max(ans,lis[i]+seg.query(F[i],F[i]+d));
        seg.update(F[i],suflis[i]);
    }
    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