oj.uz

Submission #957875

# Submission time Handle Problem Language Result Execution time Memory
957875 2024-04-04T12:42:25 Z vjudge1 Abracadabra (CEOI22_abracadabra) C++17
25 / 100
 1670 ms 16380 KB 
#include<stdio.h>
#include<stdlib.h>

#define N 200004
int n,a[N],t[N],q,sz[N],at[N],zz[1000005];

void upd(int p,int k) { for(;p<N;p|=p+1)t[p]+=k; }
int qry(int p) {int z=0;for(;p>0;p&=p-1)z+=t[p-1];return z;}

void add(int p,int k) { sz[p]=k; upd(p,k); }
void rem(int p) { upd(p,-sz[p]); }

int grp(int x)
{
    if(x<=0)return -1;
    int p=0,v=0;
    for(int j=1<<19;j>0;j>>=1) if(p+j<=N&&v+t[p+j-1]<x)p+=j,v+=t[p-1];
    return p;
}

int ii[1000000],tt[1000000],ww[1000087],head[N],link[N],ho;

void shuffle()
{
    static int done=0;
    if(done)return;
    int g1=grp(n/2),g2=grp(n/2+1);
    if(g1!=g2){done=1;return;}
    int rl=qry(g1);
    int st=at[g1];
    int md=n/2-rl+at[g1];
    int ed=at[g1]+sz[g1];
    for(int l=md,j=md;j<=ed;++j) if(j==ed||a[j]>a[l])add(a[l],j-l),l=j;
    rem(g1);
    add(g1,n/2-rl);
}

int main()
{
    scanf("%d%d",&n,&q);
    if(q>100000)return 1;
    for(int i=1;i<=n;++i)scanf("%d",a+i),at[a[i]]=i;
    for(int l=1,i=1;i<=n+1;++i) if(i==n+1||a[i]>a[l]) add(a[l],i-l),l=i;

    for(int p,i=0;i<q;++i)
    {
        scanf("%d%d",tt+i,ii+i);
        if(tt[i]>n+1)tt[i]=n+1;
        ww[++ho]=i;
        link[ho]=head[tt[i]];
        head[tt[i]]=ho;
    }

    for(int i=0;i<=n+1;++i)
    {
        for(int j=head[i];j;j=link[j])
        {
            int k=ww[j];
            int gg=grp(ii[k]);
            int idx=ii[k]-qry(gg);
            zz[k]=a[at[gg]+idx-1];
        }
        shuffle();
    }

    for(int i=0;i<q;++i)printf("%d\n",zz[i]);

    return 0;
}

Compilation message

Main.cpp: In function 'void shuffle()':
Main.cpp:30:9: warning: unused variable 'st' [-Wunused-variable]
   30 |     int st=at[g1];
      |         ^~
Main.cpp: In function 'int main()':
Main.cpp:45:13: warning: unused variable 'p' [-Wunused-variable]
   45 |     for(int p,i=0;i<q;++i)
      |             ^
Main.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d%d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:42:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     for(int i=1;i<=n;++i)scanf("%d",a+i),at[a[i]]=i;
      |                          ~~~~~^~~~~~~~~~
Main.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         scanf("%d%d",tt+i,ii+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 2396 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 2396 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1626 ms 16380 KB Output is correct
2 Correct 49 ms 15956 KB Output is correct
3 Correct 1670 ms 16180 KB Output is correct
4 Correct 43 ms 15840 KB Output is correct
5 Correct 49 ms 16204 KB Output is correct
6 Correct 40 ms 15952 KB Output is correct
7 Correct 46 ms 16060 KB Output is correct
8 Correct 43 ms 15956 KB Output is correct
9 Correct 44 ms 16116 KB Output is correct
10 Correct 44 ms 16216 KB Output is correct
11 Correct 38 ms 15956 KB Output is correct
12 Correct 37 ms 15964 KB Output is correct
13 Correct 39 ms 15956 KB Output is correct
14 Correct 39 ms 16044 KB Output is correct
15 Correct 38 ms 15956 KB Output is correct
16 Correct 9 ms 12892 KB Output is correct
17 Correct 44 ms 16128 KB Output is correct
18 Correct 33 ms 15960 KB Output is correct
19 Correct 2 ms 12636 KB Output is correct
20 Correct 1 ms 12636 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 2396 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -