Submission #318037

#	Time	Username	Problem	Language	Result	Execution time	Memory
318037		Dymo	Global Warming (CEOI18_glo)	C++14	0 / 100	534 ms	10968 KiB

glo

#include<bits/stdc++.h>

using namespace std;


#define pb    push_back
#define eb   emplace_back
#define ll  int
#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[4][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;
    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;
        ll p=get(1,1,vt.size()-1,1,h-1,1)+1;
        update(1,1,vt.size(),h,t,0);
        update(1,1,vt.size(),h,p,1);
        ll h1=lower_bound(vt.begin(),vt.end(),a[i]-x)-vt.begin();
        update(1,1,vt.size(),h1,t,1);
        ans=max(ans,t);
         ans=max(ans,p);
    }
    cout <<ans<<endl;




}

Compilation message (stderr)

glo.cpp:15:15: warning: overflow in conversion from 'double' to 'int' changes value from '3.0e+18' to '2147483647' [-Woverflow]
   15 | const ll base=3e18;
      |               ^~~~
glo.cpp: In function 'int main()':
glo.cpp:52:11: warning: overflow in conversion from 'double' to 'std::vector<int>::value_type' {aka 'int'} changes value from '-1.0e+15' to '-2147483648' [-Woverflow]
   52 |     vt.pb(-1e15);
      |           ^~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25