제출 #1286546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286546		HoriaHaivas	Global Warming (CEOI18_glo)	C++20	28 / 100	2095 ms	15132 KiB

glo

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

class AINT
{
public:
    int aint[800005];

    void build(int l, int r, int val)
    {
        if (l==r)
        {
            aint[val]=0;
            return;
        }
        int mid;
        mid=(l+r)/2;
        build(l,mid,val*2);
        build(mid+1,r,val*2+1);
        aint[val]=max(aint[val*2],aint[val*2+1]);
    }

    void update(int l, int r, int val, int poz, int x)
    {
        if (l==r && l==poz)
        {
            aint[val]=x;
            return;
        }
        int mid;
        mid=(l+r)/2;
        if (poz<=mid)
        update(l,mid,val*2,poz,x);
        else
        update(mid+1,r,val*2+1,poz,x);
        aint[val]=max(aint[val*2],aint[val*2+1]);
    }

    int query(int l, int r, int val, int qa, int qb)
    {
        if (qa<=l && r<=qb)
        {
            return aint[val];
        }
        int mid,ans;
        mid=(l+r)/2;
        ans=0;
        if (qa<=mid)
            ans=max(ans,query(l,mid,val*2,qa,qb));
        if (qb>mid)
            ans=max(ans,query(mid+1,r,val*2+1,qa,qb));
        return ans;
    }
} aintpref,aintsuff,aintnush;

struct nush
{
    int val;
    int poz;
};

bool cmppref(nush a, nush b)
{
    if (a.val!=b.val)
    return a.val<b.val;
    else
    return a.poz>b.poz;
}

bool cmpsuff(nush a, nush b)
{
    if (a.val!=b.val)
    return a.val>b.val;
    else
    return a.poz<b.poz;
}

bool init(nush a, nush b)
{
    return a.poz<b.poz;
}

int pref[200005];
int suff[200005];
nush a[200005];

signed main()
{
    /*
    ifstream fin("camere.in");
    ofstream fout("camere.out");
    */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,x,i,j,ans;
    cin >> n >> x;
    for (i=1;i<=n;i++)
    {
        cin >> a[i].val;
        a[i].poz=i;
    }
    sort(a+1,a+1+n,cmppref);
    aintpref.build(1,n,1);
    for (i=1;i<=n;i++)
    {
         pref[a[i].poz]=1;
         pref[a[i].poz]=max(pref[a[i].poz],aintpref.query(1,n,1,1,max(1LL,a[i].poz-1))+1);
         aintpref.update(1,n,1,a[i].poz,pref[a[i].poz]);
    }
    sort(a+1,a+1+n,cmpsuff);
    aintsuff.build(1,n,1);
    for (i=1;i<=n;i++)
    {
         suff[a[i].poz]=1;
         suff[a[i].poz]=max(suff[a[i].poz],aintsuff.query(1,n,1,min(a[i].poz+1,n),n)+1);
         aintsuff.update(1,n,1,a[i].poz,suff[a[i].poz]);
    }
    sort(a+1,a+1+n,init);
    ans=0;
    for (i=1;i<=n;i++)
    {
         for (j=i+1;j<=n;j++)
         {
              if (a[i].val-x<a[j].val)
                  ans=max(ans,pref[i]+suff[j]);
         }
    }
    cout << ans;
    return 0;
}

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