Submission #483317

#	Time	Username	Problem	Language	Result	Execution time	Memory
483317		MOUF_MAHMALAT	Global Warming (CEOI18_glo)	C++14	100 / 100	1170 ms	191804 KiB

glo

#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
#define F first
#define S second
using namespace std;
typedef int ll;
const ll ee=1e9;
struct node
{
    node*l=0,*r=0;
    ll val=0;
} *lis,*lds;
ll n,k,a[200009],ans;
map<ll,vector<ll> >v;
ll best_lis(node*d,ll l,ll r,ll x)
{
    if(l>x||d==0)
        return 0;
    if(r<=x)
        return d->val;
    ll m=(l+r)/2;
    return max(best_lis(d->l,l,m,x),best_lis(d->r,m+1,r,x));
}
ll best_lds(node*d,ll l,ll r,ll x)
{
    if(r<x||d==0)
        return 0;
    if(l>=x)
        return d->val;
    ll m=(l+r)/2;
    return max(best_lds(d->l,l,m,x),best_lds(d->r,m+1,r,x));
}
void up_lis(node*d,ll l,ll r,ll id)
{
    if(l==r)
    {
        if(v[l].empty())
            d->val=0;
        else
            d->val=v[l].back();
        return;
    }
    ll m=(l+r)/2;
    if(id<=m)
    {
        if(d->l==0)
            d->l=new node;
        up_lis(d->l,l,m,id);
    }
    else
    {
        if(d->r==0)
            d->r=new node;
        up_lis(d->r,m+1,r,id);
    }
    d->val=0;
    if(d->l!=0)
        d->val=d->l->val;
    if(d->r!=0)
        d->val=max(d->val,d->r->val);
}
void up_lds(node*d,ll l,ll r,ll id,ll x)
{
    if(l==r)
        return void(d->val=x);
    ll m=(l+r)/2;
    if(id<=m)
    {
        if(d->l==0)
            d->l=new node;
        up_lds(d->l,l,m,id,x);
    }
    else
    {
        if(d->r==0)
            d->r=new node;
        up_lds(d->r,m+1,r,id,x);
    }
    d->val=0;
    if(d->l!=0)
        d->val=d->l->val;
    if(d->r!=0)
        d->val=max(d->val,d->r->val);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    lis=new node;
    lds=new node;
    cin>>n>>k;
    for(ll i=1; i<=n; i++)
    {
        cin>>a[i];
        ll op=best_lis(lis,0,ee,a[i]-1)+1;
        v[a[i]].push_back(op);
        up_lis(lis,0,ee,a[i]);
    }
    for(ll i=n; i; i--)
    {
        v[a[i]].pop_back();
        up_lis(lis,0,ee,a[i]);
        ll op=best_lds(lds,0,ee,a[i]+1)+1;
        up_lds(lds,0,ee,a[i],op);
        op+=best_lis(lis,0,ee,a[i]+k-1);
        ans=max(ans,op);
    }
    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