Submission #1096708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096708		MinhTri2k8	Global Warming (CEOI18_glo)	C++14	10 / 100	2051 ms	6684 KiB

glo

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second;
int n,t[1200010],x,a[200010],b[200010];
void update(int id, int l, int r, int u,int val)
{
    if (u<l || r<u) return;
    if (l==r)
    {
        t[id]=val;
        return;
    }
    int mid=(l+r)/2;
    update(id*2,l,mid,u,val);
    update(id*2+1,mid+1,r,u,val);
    t[id]=max(t[id*2],t[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 t[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 solve1()
{
    int res=0;
    for (int i=1;i<=n;i++) b[i]=a[i];
    sort(b+1,b+1+n);
    for (int i=1;i<=n;i++)
    {
        a[i]=lower_bound(b+1,b+1+n,a[i])-b;
//        cout<<a[i]<<' ';
        a[i]++;
//        cout<<a[i]<<' ';
    }
    for (int i=1;i<=n;i++)
    {
        int tam=get(1,1,300000,1,a[i]-1);
        update(1,1,300000,a[i],tam+1);
        res=max(res,tam+1);
    }
    //cout<<get(1,1,300000,1,a[8])<<' ';
    cout<<res;
}
void solve2()
{
    int res=0;
    int c[200010];
    for (int j=1;j<=n;j++)
    {
        for (int i=0;i<=4*10000;i++) t[i]=0;
        for (int i=1;i<=n;i++) b[i]=a[i];
        for (int i=1;i<=n;i++) c[i]=a[i];
        for (int i=j+1;i<=n;i++) c[i]=a[i]+x,b[i]=a[i]+x;
//        for (int i=1;i<=n;i++) cout<<b[i]<<' ';

        sort(b+1,b+1+n);
        for (int i=1;i<=n;i++)
        {
            c[i]=lower_bound(b+1,b+1+n,c[i])-b;
//        cout<<a[i]<<' ';
            c[i]++;
//        cout<<a[i]<<' ';
        }
//        for (int i=1;i<=n;i++) cout<<c[i]<<' ';cout<<'\n';
        for (int i=1;i<=n;i++)
        {
            int tam=get(1,1,40000,1,c[i]-1);
            update(1,1,40000,c[i],tam+1);
//            cout<<tam<<' ';
            res=max(res,tam+1);
        }
        //cout<<get(1,1,300000,1,a[8])<<' ';
//        cout<<res<<'\n';
    }
    cout<<res;
}
int main()
{
    //freopen("daydep.inp","r",stdin);
    //freopen("daydep.out","w",stdout);
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>x;
    for (int i=1;i<=n;i++) cin>>a[i];
    if (x==0) solve1();
    else solve2();
return 0;
}

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