Submission #318040

#	Time	Username	Problem	Language	Result	Execution time	Memory
318040		Dymo	Global Warming (CEOI18_glo)	C++14	100 / 100	605 ms	23760 KiB

glo

#include<bits/stdc++.h>

using namespace std;


#define pb    push_back
#define eb   emplace_back
#define ll  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"
const ll maxn=5e5+50;
const ll mod =998244353 ;
const ll base=3e18;
vector<ll> vt;

ll st[2][4*maxn];
ll a[maxn];

void update(ll id,ll left,ll right,ll x,ll diff,ll t )
{
    if (x>right||x<left) return ;
    if (right==left )
    {
        st[t][id]=max(st[t][id],diff);
        return ;
    }
    ll mid=(left+right)/2;
    update(id*2,left,mid, x, diff,t);
    update(id*2+1, mid+1, right, x, diff,t);
    st[t][id]=max(st[t][id*2],st[t][id*2+1]);
}
ll get(ll id,ll left,ll right,ll x,ll y,ll t)
{
    if (x>right||y<left||x> y) return 0;
    if (x<=left&&y>=right)
    {
        return st[t][id];
    }
    ll mid=(left+right)/2;
    return max(get(id*2,left,mid, x, y, t ),get(id*2+1, mid+1, right, x, y, t));

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n, x ;
    cin>> n>> x ;
    vt.pb(-1e15);
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
        vt.pb(a[i]);
        vt.pb(a[i]-x);
    }
    sort(vt.begin(),vt.end());
    vt.resize(unique(vt.begin(),vt.end())-vt.begin());
    ll ans=0;
    //cout <<vt.size()<<endl;
    /*for (auto to:vt)
    {
        cout <<to<<endl;
    }*/
   for (int i=1;i<=n;i++)
    {
        ll h=lower_bound(vt.begin(),vt.end(),a[i])-vt.begin();
        ll t=get(1,1,vt.size()-1,1,h-1,0)+1;
      //  cout <<1<<" "<<1<<" "<<vt.size()-1<<" "<<1<<" "<<h-1<<" "<<0<<endl;
        ll p=get(1,1,vt.size()-1,1,h-1,1)+1;
        update(1,1,vt.size()-1,h,t,0);
      //  cout <<1<<" "<<1<<" "<<vt.size()<<"
         update(1,1,vt.size()-1,h,p,1);
        ll h1=lower_bound(vt.begin(),vt.end(),a[i]-x)-vt.begin();
         update(1,1,vt.size()-1,h1,t,1);
        //cout <<t<<" "<<p<<" "<<h<<endl;
       // cout <<h<<" "<<h-1<<endl;
        ans=max(ans,t);
        ans=max(ans,p);
    }
    //update(1,1,vt.size()-1,4,2,0);
   // cout <<get(1,1,vt.size()-1,1,3,0)<<endl ;
    cout <<ans<<endl;
/*10 10
1 1 1 1 1 1 2 2 2 1
*/



}

• 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