Submission #1137981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137981		trinhvtuan	Global Warming (CEOI18_glo)	C++20	100 / 100	480 ms	32732 KiB

glo

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
typedef pair<int,int>i2;
int k,c,d,x,y,z,n,ans;
int i,j;
int st[4*N],g[N],h[N],f[N],b[N];
struct gv
{
    int val,vitri;
};
gv a[N];
bool cmp(gv x,gv y)
{
    if (x.val<y.val) return true;
    if (x.val==y.val && x.vitri>y.vitri) return true;
    return false;
}
bool cmp1(gv x,gv y)
{
    if (x.val>y.val) return true;
    if (x.val==y.val && x.vitri<y.vitri) return true;
    return false;
}
void update(int id,int l,int r,int i,int val)
{
    if (i<l || r<i) return;
    if (l==r)
    {
        st[id]=val;
        return;
    }
    int mid=(l+r)/2;
    update(id*2,l,mid,i,val);
    update(id*2+1,mid+1,r,i,val);
    st[id]=max(st[id*2],st[id*2+1]);
}
int get(int id,int l,int r,int u,int v)
{
    if (v<l || r<u) return 0;
    if (u<=l && r<=v) return st[id];
    int mid=(l+r)/2;
    return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
namespace sub2
{
    void solve()
    {
        for (int i=1;i<=n;i++)
        {
//            cout<<g[i]<<" "<<h[i]<<"\n";
            c=b[i];
            for (int j=i+1;j<=n;j++)
            {
                d=b[j]+k;
                if (c<d) ans=max(ans,g[i]+h[j]);
            }
        }
        for (int i=1;i<=n;i++)
        {
            d=b[i];
            for (int j=1;j<i;j++)
            {
                c=b[j]-k;
                if (c<d) ans=max(ans,g[j]+h[i]);
            }
        }
        cout<<ans;
    }
}
namespace sub3
{
    vector<int>tt;
    map<int,int>mp;
    int id;
    int st[8*N];
    void nen()
    {
        sort(tt.begin(),tt.end());
        id++; mp[tt[0]]=id;
        for (int i=1;i<tt.size();i++)
        if (tt[i]!=tt[i-1])
        {
            id++; mp[tt[i]]=id;
        }
    }
    void update(int id,int l,int r,int i,int val)
    {
        if (i<l || r<i) return;
        if (l==r)
        {
            st[id]=val;
            return;
        }
        int mid=(l+r)/2;
        update(id*2,l,mid,i,val);
        update(id*2+1,mid+1,r,i,val);
        st[id]=max(st[id*2],st[id*2+1]);
    }
    int get(int id,int l,int r,int u,int v)
    {
        if (v<l || r<u) return 0;
        if (u<=l && r<=v) return st[id];
        int mid=(l+r)/2;
        return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
    }
    void solve()
    {
        for (int i=1;i<=4*n;i++)
        st[i]=0;
        for (int i=1;i<=n;i++)
        {
            tt.push_back(b[i]+k);
            tt.push_back(b[i]+1);
        }
        nen();
        for (int i=n;i>=1;i--)
        {
            c=get(1,1,id,mp[b[i]+1],id);
//            cout<<g[i]<<" "<<c<<" "<<b[i]+k<<"\n";
            ans=max(ans,g[i]+c);
            update(1,1,id,mp[b[i]+k],h[i]);
        }
        cout<<ans;
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>k;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i].val; a[i].vitri=i;
        b[i]=a[i].val;
    }
    sort(a+1,a+n+1,cmp);
    for (int i=1;i<=n;i++)
    {
        z=a[i].vitri;
        c=get(1,1,n,1,z);
        g[z]=c+1;
        ans=max(ans,g[z]);
        update(1,1,n,z,g[z]);
    }
//    cout<<n<<"\n";
    for (int i=1;i<=4*n;i++)
    st[i]=0;
//    cout<<n<<"\n";
    sort(a+1,a+n+1,cmp1);
//    cout<<n<<"\n";
    for (int i=1;i<=n;i++)
    {
        z=a[i].vitri;
        c=get(1,1,n,z,n);
        h[z]=c+1;
        update(1,1,n,z,h[z]);
    }
//    cout<<n<<"\n";
    for (int i=n;i>=1;i--)
    {
        f[i]=max(f[i+1],b[i]);
    }
    if (n<=1000) sub2::solve(); else
    sub3::solve();
}

• 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