Submission #1096267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096267		trinhvtuan	Global Warming (CEOI18_glo)	C++17	38 / 100	2059 ms	12752 KiB

glo

#include <bits/stdc++.h>
using namespace std;
long long k,c,d,x,y,z,n,kq,kq1;
int i,j;
long long ans[1000001],b[1000001],st[1000001];
struct gv
{
    long long val,vitri;
};
gv a[1000001];
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;
}
void buildtree(int id,int l,int r)
{
    if (l==r)
    {
        st[id]=0; return;
    }
    int mid=(l+r)/2;
    buildtree(id*2,l,mid);
    buildtree(id*2+1,mid+1,r);
    st[id]=st[id*2]+st[id*2+1];
}
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]);
}
long long 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()
{
    buildtree(1,1,n); kq=0;
    sort(a+1,a+n+1,cmp);
    for (int i=1;i<=n;i++)
    {
        c=get(1,1,n,1,a[i].vitri)+1;
        ans[a[i].vitri]=c;
        update(1,1,n,a[i].vitri,c);
    }
    for (int i=1;i<=n;i++)
    kq=max(kq,ans[i]);
    //cout<<kq<<"\n";
    kq1=max(kq1,kq);
}
void sub1()
{
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<i;j++)
        {
            a[j].val=b[j]; a[j].vitri=j;
        }
        for (int j=i;j<=n;j++)
        {
            a[j].val=b[j]+k; a[j].vitri=j;
        }
        solve();
    }
    cout<<kq1;
}
void sub2()
{
    for (int i=1;i<=n;i++)
    {
        a[i].val=b[i]; a[i].vitri=i;
    }
    sort(a+1,a+n+1,cmp);
    for (int i=1;i<=n;i++)
    {
        c=get(1,1,n,1,a[i].vitri)+1;
        ans[a[i].vitri]=c;
        update(1,1,n,a[i].vitri,c);
    }
    for (int i=1;i<=n;i++)
    kq=max(kq,ans[i]);
    cout<<kq;
}
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>>k;
    for (int i=1;i<=n;i++)
    {
        cin>>b[i];
    }
    if (k!=0) sub1(); else
    sub2();
}

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