Submission #972246

#	Time	Username	Problem	Language	Result	Execution time	Memory
972246		sofija6	Global Warming (CEOI18_glo)	C++14	100 / 100	525 ms	39464 KiB

glo

#include <bits/stdc++.h>
#define ll long long
#define MAXN 200010
using namespace std;
ll n,sz,t[MAXN],a[MAXN],l[MAXN],r[MAXN],lisl[MAXN],lisr[MAXN];
map<ll,ll> val;
set<ll> s;
vector<ll> v;
struct seg_tree
{
    vector<ll> st;
    void Init()
    {
        st.clear();
        sz=1;
        while (sz<n)
            sz <<= 1;
        st.resize(2*sz+2);
    }
    void Update(ll pos,ll val,ll x,ll lx,ll rx)
    {
        if (lx==rx)
        {
            st[x]=val;
            return;
        }
        ll mid=(lx+rx)/2;
        if (pos<=mid)
            Update(pos,val,2*x,lx,mid);
        else
            Update(pos,val,2*x+1,mid+1,rx);
        st[x]=max(st[2*x],st[2*x+1]);
    }
    ll Calc(ll l,ll r,ll x,ll lx,ll rx)
    {
        if (lx>r || rx<l)
            return 0;
        if (lx>=l && rx<=r)
            return st[x];
        ll mid=(lx+rx)/2;
        return max(Calc(l,r,2*x,lx,mid),Calc(l,r,2*x+1,mid+1,rx));
    }
};
seg_tree S;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll x,cur=1;
    cin >> n >> x;
    for (ll i=1;i<=n;i++)
    {
        cin >> t[i];
        s.insert(t[i]);
    }
    for (ll i : s)
    {
        val[i]=cur++;
        v.push_back(i);
    }
    for (ll i : v)
    {
        auto it=upper_bound(v.begin(),v.end(),i-1+x);
        if (it!=v.begin())
        {
            it--;
            l[val[i]]=val[*it];
        }
        it=lower_bound(v.begin(),v.end(),i+1-x);
        if (it!=v.end())
            r[val[i]]=val[*it];
    }
    S.Init();
    for (ll i=1;i<=n;i++)
    {
        a[i]=val[t[i]];
        ll maxx=0;
        if (a[i]!=1)
            maxx=S.Calc(1,a[i]-1,1,1,sz);
        lisl[i]=maxx+1;
        S.Update(a[i],maxx+1,1,1,sz);
    }
    S.Init();
    for (ll i=n;i>0;i--)
    {
        ll maxx=0;
        if (a[i]!=n)
            maxx=S.Calc(a[i]+1,n,1,1,sz);
        lisr[i]=maxx+1;
        S.Update(a[i],maxx+1,1,1,sz);
    }
    S.Init();
    ll ans=0;
    for (ll i=1;i<=n;i++)
    {
        if (l[a[i]])
            ans=max(ans,S.Calc(1,l[a[i]],1,1,sz)+lisr[i]);
        S.Update(a[i],lisl[i],1,1,sz);
    }
    S.Init();
    for (ll i=n;i>0;i--)
    {
        if (r[a[i]])
            ans=max(ans,lisl[i]+S.Calc(r[a[i]],n,1,1,sz));
        S.Update(a[i],lisr[i],1,1,sz);
    }
    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