oj.uz

Submission #957858

# Submission time Handle Problem Language Result Execution time Memory
957858 2024-04-04T12:22:27 Z vjudge1 Abracadabra (CEOI22_abracadabra) C
35 / 100
 840 ms 27948 KB 
#include<stdio.h>
#include<stdlib.h>

#define N 100004
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 258 ms 20004 KB Output is correct
2 Correct 267 ms 25068 KB Output is correct
3 Correct 253 ms 24472 KB Output is correct
4 Correct 244 ms 23248 KB Output is correct
5 Correct 255 ms 26196 KB Output is correct
6 Correct 243 ms 26704 KB Output is correct
7 Correct 272 ms 27948 KB Output is correct
8 Correct 244 ms 25172 KB Output is correct
9 Correct 254 ms 24064 KB Output is correct
10 Correct 246 ms 23844 KB Output is correct
11 Correct 246 ms 24016 KB Output is correct
12 Correct 245 ms 22072 KB Output is correct
13 Correct 253 ms 22816 KB Output is correct
14 Correct 300 ms 26052 KB Output is correct
15 Correct 258 ms 23276 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 254 ms 21816 KB Output is correct
18 Correct 238 ms 21844 KB Output is correct
19 Correct 1 ms 2644 KB Output is correct
20 Correct 1 ms 2392 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 5724 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 840 ms 8316 KB Output is correct
2 Correct 60 ms 8784 KB Output is correct
3 Correct 807 ms 8252 KB Output is correct
4 Correct 50 ms 8848 KB Output is correct
5 Correct 52 ms 8660 KB Output is correct
6 Correct 51 ms 8528 KB Output is correct
7 Correct 50 ms 8784 KB Output is correct
8 Correct 53 ms 8528 KB Output is correct
9 Correct 49 ms 8632 KB Output is correct
10 Correct 53 ms 8968 KB Output is correct
11 Correct 55 ms 9212 KB Output is correct
12 Correct 54 ms 9000 KB Output is correct
13 Correct 48 ms 8788 KB Output is correct
14 Correct 44 ms 9112 KB Output is correct
15 Correct 48 ms 8828 KB Output is correct
16 Correct 17 ms 6748 KB Output is correct
17 Correct 51 ms 8624 KB Output is correct
18 Correct 48 ms 7812 KB Output is correct
19 Correct 1 ms 2592 KB Output is correct
20 Correct 1 ms 2648 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 20004 KB Output is correct
2 Correct 267 ms 25068 KB Output is correct
3 Correct 253 ms 24472 KB Output is correct
4 Correct 244 ms 23248 KB Output is correct
5 Correct 255 ms 26196 KB Output is correct
6 Correct 243 ms 26704 KB Output is correct
7 Correct 272 ms 27948 KB Output is correct
8 Correct 244 ms 25172 KB Output is correct
9 Correct 254 ms 24064 KB Output is correct
10 Correct 246 ms 23844 KB Output is correct
11 Correct 246 ms 24016 KB Output is correct
12 Correct 245 ms 22072 KB Output is correct
13 Correct 253 ms 22816 KB Output is correct
14 Correct 300 ms 26052 KB Output is correct
15 Correct 258 ms 23276 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 254 ms 21816 KB Output is correct
18 Correct 238 ms 21844 KB Output is correct
19 Correct 1 ms 2644 KB Output is correct
20 Correct 1 ms 2392 KB Output is correct
21 Runtime error 10 ms 5724 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -