Submission #830651

#	Time	Username	Problem	Language	Result	Execution time	Memory
830651		Amylopectin	Abracadabra (CEOI22_abracadabra)	C++14	100 / 100	603 ms	41912 KiB

Main

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
using namespace std;
const int mxn = 4e6 + 10;
struct we
{
    int tt,ii,idx,vall;
};
bool cmp(const struct we &l,const struct we &r)
{
    return l.tt < r.tt;
}
bool cmp2(const struct we &l,const struct we &r)
{
    return l.idx < r.idx;
}
struct we sot[mxn] = {};
int ta[mxn] = {},fa[mxn] = {},u[mxn] = {},li[mxn] = {},cma = 0,se[mxn] = {}
,fipo,lef,mat[mxn] = {},va[mxn] = {},poi[mxn] = {},stac[mxn] = {};
int ad(int cl,int cr,int no,int tar,int ava)
{
    if(cl > tar || cr < tar)
    {
        return 0;
    }
    if(cl == cr)
    {
        se[no] = ava;
        return 0;
    }
    int mid = (cl+cr) / 2;
    ad(cl,mid,no*2,tar,ava);
    ad(mid+1,cr,no*2+1,tar,ava);
    se[no] = se[no*2] + se[no*2+1];
    return 0;
}
int fii(int cl,int cr,int no,int fiva)
{
    if(cl == cr)
    {
        fipo = cl;
        lef = fiva;
        return 0;
    }
    int mid = (cl+cr) / 2;
    if(se[no*2] < fiva)
    {
        fiva -= se[no*2];
        fii(mid+1,cr,no*2+1,fiva);
    }
    else 
    {
        fii(cl,mid,no*2,fiva);
    }
    return 0;
}
int main()
{
    // freopen("t7.out","w",stdout);
    int i,j,n,q,k,m,cn,cm,fn,fm,cl,cr,cru,ru,cbe,bep,tst = 0,clim;
    scanf("%d %d",&n,&q);
    stac[0] = n+1;
    for(i=1; i<=n; i++)
    {
        poi[i] = -1;
    }
    for(i=0; i<n; i++)
    {
        scanf("%d",&ta[i]);
        mat[ta[i]] = i;
        while(stac[tst] < ta[i])
        {
            poi[stac[tst]] = ta[i];
            tst --;
        }
        tst ++;
        stac[tst] = ta[i];
    }
    for(i=0; i<q; i++)
    {
        scanf("%d %d",&cn,&cm);
        sot[i] = {cn,cm,i,-1};
    }
    cbe = ta[0];
    bep = 0;
    for(i=1; i<n/2; i++)
    {
        if(ta[i] > cbe)
        {
            va[cbe] = i-bep;
            ad(1,n,1,cbe,i-bep);
            bep = i;
            cbe = ta[i];
        }
    }
    va[cbe] = n/2-bep;
    ad(1,n,1,cbe,n/2-bep);
    bep = n/2;
    cbe = ta[n/2];
    for(i=n/2+1; i<n; i++)
    {
        if(ta[i] > cbe)
        {
            va[cbe] = i-bep;
            ad(1,n,1,cbe,i-bep);
            bep = i;
            cbe = ta[i];
        }
    }
    va[cbe] = n-bep;
    ad(1,n,1,cbe,n-bep);
    sort(sot,sot+q,cmp);
    // for(j=0; j<n; j++)
    //     {
    //         printf("%d ",ta[j]);
    //     }
    //     printf("\n");
    // re(-1,n,0);
    // printf("%d\n",cma);
    ru = 0;
    while(ru < q && sot[ru].tt == 0)
        {
            sot[ru].vall = ta[sot[ru].ii-1];
            ru ++;
        }
    for(i=1; i<=n; i++)
    {
        while(ru < q && sot[ru].tt == i)
        {
            fii(1,n,1,sot[ru].ii);
            sot[ru].vall = ta[mat[fipo]+lef-1];
            ru ++;
        }
        if(ru == q)
        {
            break;
        }
        fii(1,n,1,n/2);
        cn = fipo;
        cm = lef;
        clim = mat[cn] + va[cn];
        if(va[cn] == cm)
        {
            break;
        }
        ad(1,n,1,cn,lef);
        va[cn] = lef;
        cn = ta[mat[cn]+lef];
        while(1)
        {
            fn = poi[cn];
            if(fn == -1)
            {
                break;
            }
            if(mat[fn] >= clim)
            {
                break;
            }
            ad(1,n,1,cn,mat[fn] - mat[cn]);
            va[cn] = mat[fn] - mat[cn];
            cn = fn;
        }
        // fn = 
        // fm = va[cn] - lef;
        
        ad(1,n,1,cn,clim - mat[cn]);
        va[cn] = clim - mat[cn];
        // va[fn] = fm;

        // cl = 0;
        // cr = n/2;
        // for(j=0; j<n; j++)
        // {
        //     if(cl == n/2)
        //     {
        //         fa[j] = ta[cr];
        //         cr ++;
        //     }
        //     else if(cr == n)
        //     {
        //         fa[j] = ta[cl];
        //         cl ++;
        //     }
        //     else if(ta[cl] < ta[cr])
        //     {
        //         fa[j] = ta[cl];
        //         cl ++;
        //     }
        //     else 
        //     {
        //         fa[j] = ta[cr];
        //         cr ++;
        //     }
        // }
        // for(j=0; j<n; j++)
        // {
        //     ta[j] = fa[j];
            
        //     // printf("%d ",fa[j]);
        // }
        // while(ru < q && sot[ru].tt == i)
        // {
        //     fii(1,n,1,sot[ru].ii);
        //     sot[ru].vall = ta[mat[fipo]+lef-1];
        //     ru ++;
        // }
        // if(ru == q)
        // {
        //     break;
        // }
        // printf("\n");
    }
    while(ru < q)
        {
            fii(1,n,1,sot[ru].ii);
            sot[ru].vall = ta[mat[fipo]+lef-1];
            ru ++;
        }
    sort(sot,sot+q,cmp2);
    for(i=0; i<q; i++)
    {
        printf("%d\n",sot[i].vall);
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:62:11: warning: unused variable 'j' [-Wunused-variable]
   62 |     int i,j,n,q,k,m,cn,cm,fn,fm,cl,cr,cru,ru,cbe,bep,tst = 0,clim;
      |           ^
Main.cpp:62:17: warning: unused variable 'k' [-Wunused-variable]
   62 |     int i,j,n,q,k,m,cn,cm,fn,fm,cl,cr,cru,ru,cbe,bep,tst = 0,clim;
      |                 ^
Main.cpp:62:19: warning: unused variable 'm' [-Wunused-variable]
   62 |     int i,j,n,q,k,m,cn,cm,fn,fm,cl,cr,cru,ru,cbe,bep,tst = 0,clim;
      |                   ^
Main.cpp:62:30: warning: unused variable 'fm' [-Wunused-variable]
   62 |     int i,j,n,q,k,m,cn,cm,fn,fm,cl,cr,cru,ru,cbe,bep,tst = 0,clim;
      |                              ^~
Main.cpp:62:33: warning: unused variable 'cl' [-Wunused-variable]
   62 |     int i,j,n,q,k,m,cn,cm,fn,fm,cl,cr,cru,ru,cbe,bep,tst = 0,clim;
      |                                 ^~
Main.cpp:62:36: warning: unused variable 'cr' [-Wunused-variable]
   62 |     int i,j,n,q,k,m,cn,cm,fn,fm,cl,cr,cru,ru,cbe,bep,tst = 0,clim;
      |                                    ^~
Main.cpp:62:39: warning: unused variable 'cru' [-Wunused-variable]
   62 |     int i,j,n,q,k,m,cn,cm,fn,fm,cl,cr,cru,ru,cbe,bep,tst = 0,clim;
      |                                       ^~~
Main.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     scanf("%d %d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
Main.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         scanf("%d",&ta[i]);
      |         ~~~~~^~~~~~~~~~~~~
Main.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         scanf("%d %d",&cn,&cm);
      |         ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25