oj.uz

Submission #957859

# Submission time Handle Problem Language Result Execution time Memory
957859 2024-04-04T12:23:06 Z vjudge1 Abracadabra (CEOI22_abracadabra) C
35 / 100
 3000 ms 31552 KB 
#include<stdio.h>
#include<stdlib.h>

#define N 200004
int n,a[N],t[N],q,sz[N],at[N],*eh[N],eo[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;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<<20;j>0;j>>=1) if(p+j<=N&&v+t[p+j-1]<x)p+=j,v+=t[p-1];
    return p;
}

void append(int i,int j)
{
    int o=eo[i]++;
    if(o>=2&&(o&o-1)==0)eh[i]=(int*)realloc(eh[i],2*o*sizeof**eh);
    eh[i][o]=j;
}

void shuffle()
{
    int g1=grp(n/2),g2=grp(n/2+1);
    if(g1!=g2)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);
    for(int i=1;i<=n;++i)scanf("%d",a+i),at[a[i]]=i;
    a[n+1]=n+1;
    for(int l=1,i=1;i<=n+1;++i) if(a[i]>a[l]) add(a[l],i-l),l=i;

    for(int i=0;i<=n+1;++i)eh[i]=(int*)realloc(0,2*sizeof**eh);

    for(int t,p,i=0;i<q;++i)
    {
        scanf("%d%d",&t,&p);
        if(t>n)t=n+1;
        append(t,i),append(t,p);
    }

    for(int i=0;i<=n+1;++i)
    {
        for(int j=0;j<eo[i];j+=2)
        {
            int gg=grp(eh[i][j+1]);
            int idx=eh[i][j+1]-qry(gg);
            zz[eh[i][j]]=a[at[gg]+idx-1];
        }
        shuffle();
    }

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

    return 0;
}

Compilation message

Main.c: In function 'append':
Main.c:25:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   25 |     if(o>=2&&(o&o-1)==0)eh[i]=(int*)realloc(eh[i],2*o*sizeof**eh);
      |                 ~^~
Main.c: In function 'shuffle':
Main.c:34:9: warning: unused variable 'st' [-Wunused-variable]
   34 |     int st=at[g1];
      |         ^~
Main.c: In function 'main':
Main.c:44:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%d%d",&n,&q);
      |     ^~~~~~~~~~~~~~~~~~~
Main.c:45:26: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     for(int i=1;i<=n;++i)scanf("%d",a+i),at[a[i]]=i;
      |                          ^~~~~~~~~~~~~~~
Main.c:53:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%d%d",&t,&p);
      |         ^~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 24404 KB Output is correct
2 Correct 284 ms 22868 KB Output is correct
3 Correct 260 ms 22404 KB Output is correct
4 Correct 251 ms 22168 KB Output is correct
5 Correct 271 ms 24400 KB Output is correct
6 Correct 267 ms 25168 KB Output is correct
7 Correct 266 ms 25684 KB Output is correct
8 Correct 289 ms 23636 KB Output is correct
9 Correct 269 ms 22804 KB Output is correct
10 Correct 269 ms 22268 KB Output is correct
11 Correct 272 ms 22612 KB Output is correct
12 Correct 261 ms 21404 KB Output is correct
13 Correct 258 ms 21548 KB Output is correct
14 Correct 286 ms 24148 KB Output is correct
15 Correct 265 ms 22000 KB Output is correct
16 Correct 2 ms 6488 KB Output is correct
17 Correct 259 ms 21484 KB Output is correct
18 Correct 238 ms 21008 KB Output is correct
19 Correct 1 ms 6488 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3044 ms 31552 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 902 ms 10952 KB Output is correct
2 Correct 61 ms 11600 KB Output is correct
3 Correct 828 ms 11088 KB Output is correct
4 Correct 55 ms 11604 KB Output is correct
5 Correct 58 ms 11264 KB Output is correct
6 Correct 52 ms 11348 KB Output is correct
7 Correct 57 ms 11424 KB Output is correct
8 Correct 60 ms 11432 KB Output is correct
9 Correct 57 ms 11336 KB Output is correct
10 Correct 50 ms 11604 KB Output is correct
11 Correct 53 ms 11948 KB Output is correct
12 Correct 52 ms 11600 KB Output is correct
13 Correct 55 ms 11436 KB Output is correct
14 Correct 51 ms 11856 KB Output is correct
15 Correct 50 ms 11752 KB Output is correct
16 Correct 24 ms 9560 KB Output is correct
17 Correct 53 ms 11356 KB Output is correct
18 Correct 49 ms 11368 KB Output is correct
19 Correct 1 ms 6488 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 24404 KB Output is correct
2 Correct 284 ms 22868 KB Output is correct
3 Correct 260 ms 22404 KB Output is correct
4 Correct 251 ms 22168 KB Output is correct
5 Correct 271 ms 24400 KB Output is correct
6 Correct 267 ms 25168 KB Output is correct
7 Correct 266 ms 25684 KB Output is correct
8 Correct 289 ms 23636 KB Output is correct
9 Correct 269 ms 22804 KB Output is correct
10 Correct 269 ms 22268 KB Output is correct
11 Correct 272 ms 22612 KB Output is correct
12 Correct 261 ms 21404 KB Output is correct
13 Correct 258 ms 21548 KB Output is correct
14 Correct 286 ms 24148 KB Output is correct
15 Correct 265 ms 22000 KB Output is correct
16 Correct 2 ms 6488 KB Output is correct
17 Correct 259 ms 21484 KB Output is correct
18 Correct 238 ms 21008 KB Output is correct
19 Correct 1 ms 6488 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Execution timed out 3044 ms 31552 KB Time limit exceeded
22 Halted 0 ms 0 KB -