Submission #1286549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286549		HoriaHaivas	Global Warming (CEOI18_glo)	C++20	27 / 100	230 ms	19036 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;
}

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,weat;
    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]);
    }
    ///ar trebui sortate din nou, dar cmpsuff le sorteaza fix cum trebuie
    aintnush.build(1,n,1);
    ans=0;
    weat=n;
    for (i=1;i<=n;i++)
    {
         while (weat>=1 && a[i].val-x<a[weat].val)
         {
              aintnush.update(1,n,1,a[weat].poz,suff[a[weat].poz]);
              weat--;
         }
         ans=max(ans,pref[a[i].poz]+aintnush.query(1,n,1,min(n,a[i].poz+1),n));
    }
    cout << ans;
    return 0;
}

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