Submission #1264235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264235		nhathanh	Global Warming (CEOI18_glo)	C++20	100 / 100	176 ms	11712 KiB

glo

#include<bits/stdc++.h>
using namespace std;
#define el "\n"
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
#define file(name) if(fopen(name".inp","r")){freopen(name".inp","r",stdin);freopen(name".out","w",stdout);}
const int N=2e5+10;
int n,d,a[N];
int pre[N],suf[N],id[N],seg[4*N],cnt,ans;
vector<int>temp;
bool cmp(int x,int y)
{
    return a[x]<a[y];
}
void up(int id,int l,int r,int u,int val)
{
    if(r<u||l>u) return;
    if(l==r)
    {
        seg[id]=val;
        return;
    }
    int mid=(l+r)>>1;
    up(id*2,l,mid,u,val);
    up(id*2+1,mid+1,r,u,val);
    seg[id]=max(seg[id*2],seg[id*2+1]);
}
int get(int id,int l,int r,int u,int v)
{
    if(r<u||l>v) return 0;
    if(l>=u&&r<=v)
        return seg[id];
    int mid=(l+r)>>1;
    return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
void solve(int x)
{
     while(cnt>=1&&a[id[cnt]]>a[id[x]]-d)
     {
        up(1,1,n,id[cnt],suf[id[cnt]]);
        cnt--;
     }
     ans=max(ans,pre[id[x]]+get(1,1,n,id[x]+1,n));
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin>>n>>d;
    cnt=n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        id[i]=i;
    }
    sort(id+1,id+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        int idd=lower_bound(temp.begin(),temp.end(),a[i])-temp.begin();
        pre[i]=idd+1;
        ans=max(ans,pre[i]);
        if(idd==temp.size())
            temp.push_back(a[i]);
        else
            temp[idd]=a[i];
    }
    temp.clear();
    for(int i=n;i>=1;i--)
    {
         int idd=lower_bound(temp.begin(),temp.end(),-a[i])-temp.begin();
         suf[i]=idd+1;
         if(idd==temp.size())
            temp.push_back(-a[i]);
         else
            temp[idd]=-a[i];
    }
    for(int i=n;i>=1;i--)
    {
        if(id[i]==n) continue;
        solve(i);
    }
    cout<<ans;
    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