oj.uz

Submission #830599

# Submission time Handle Problem Language Result Execution time Memory
830599 2023-08-19T08:18:01 Z Amylopectin Abracadabra (CEOI22_abracadabra) C++14
0 / 100
 447 ms 40600 KB 
#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] = {};
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("t2.out","w",stdout);
    int i,j,n,q,k,m,cn,cm,fn,fm,cl,cr,cru,ru,cbe,bep;
    scanf("%d %d",&n,&q);
    for(i=0; i<n; i++)
    {
        scanf("%d",&ta[i]);
        mat[ta[i]] = 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;
        if(va[cn] == cm)
        {
            break;
        }
        fn = ta[mat[cn]+lef];
        fm = va[cn] - lef;
        ad(1,n,1,cn,lef);
        ad(1,n,1,fn,fm);
        va[cn] = lef;
        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

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;
      |           ^
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;
      |                 ^
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;
      |                   ^
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;
      |                                 ^~
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;
      |                                    ^~
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;
      |                                       ^~~
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:66:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         scanf("%d",&ta[i]);
      |         ~~~~~^~~~~~~~~~~~~
Main.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         scanf("%d %d",&cn,&cm);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 27492 KB Output is correct
2 Correct 414 ms 27308 KB Output is correct
3 Correct 391 ms 26316 KB Output is correct
4 Correct 339 ms 25024 KB Output is correct
5 Correct 407 ms 26824 KB Output is correct
6 Correct 365 ms 25292 KB Output is correct
7 Incorrect 378 ms 27044 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 40600 KB Output is correct
2 Correct 404 ms 40184 KB Output is correct
3 Correct 319 ms 31792 KB Output is correct
4 Correct 307 ms 32668 KB Output is correct
5 Correct 318 ms 33324 KB Output is correct
6 Correct 298 ms 32088 KB Output is correct
7 Incorrect 367 ms 40012 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 6376 KB Output is correct
2 Correct 74 ms 6296 KB Output is correct
3 Correct 75 ms 6132 KB Output is correct
4 Correct 51 ms 6108 KB Output is correct
5 Correct 66 ms 6372 KB Output is correct
6 Correct 60 ms 6052 KB Output is correct
7 Incorrect 61 ms 6296 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 27492 KB Output is correct
2 Correct 414 ms 27308 KB Output is correct
3 Correct 391 ms 26316 KB Output is correct
4 Correct 339 ms 25024 KB Output is correct
5 Correct 407 ms 26824 KB Output is correct
6 Correct 365 ms 25292 KB Output is correct
7 Incorrect 378 ms 27044 KB Output isn't correct
8 Halted 0 ms 0 KB -