oj.uz

Submission #957882

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

#define N 1000004
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>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;
}

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;
    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 i=0;i<=n;++i)eh[i]=(int*)malloc(2*sizeof**eh);

    for(int t,p,i=0;i<q;++i)
    {
        scanf("%d%d",&t,&p);
        if(t>n)t=n;
        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.cpp: In function 'void append(int, int)':
Main.cpp:24:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   24 |     if(o>=2&&(o&o-1)==0)eh[i]=(int*)realloc(eh[i],2*o*sizeof**eh);
      |                 ~^~
Main.cpp: In function 'void shuffle()':
Main.cpp:33:9: warning: unused variable 'st' [-Wunused-variable]
   33 |     int st=at[g1];
      |         ^~
Main.cpp: In function 'int main()':
Main.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%d%d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:44:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     for(int i=1;i<=n;++i)scanf("%d",a+i),at[a[i]]=i;
      |                          ~~~~~^~~~~~~~~~
Main.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf("%d%d",&t,&p);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 30716 KB Output is correct
2 Correct 304 ms 29584 KB Output is correct
3 Correct 298 ms 29264 KB Output is correct
4 Correct 283 ms 28724 KB Output is correct
5 Correct 295 ms 31436 KB Output is correct
6 Correct 289 ms 32076 KB Output is correct
7 Correct 310 ms 32848 KB Output is correct
8 Correct 282 ms 30364 KB Output is correct
9 Correct 299 ms 29396 KB Output is correct
10 Correct 295 ms 29008 KB Output is correct
11 Correct 302 ms 29268 KB Output is correct
12 Correct 288 ms 27928 KB Output is correct
13 Correct 323 ms 28324 KB Output is correct
14 Correct 295 ms 30952 KB Output is correct
15 Correct 303 ms 28652 KB Output is correct
16 Correct 2 ms 12636 KB Output is correct
17 Correct 278 ms 27804 KB Output is correct
18 Correct 272 ms 27664 KB Output is correct
19 Correct 2 ms 12636 KB Output is correct
20 Correct 2 ms 12636 KB Output is correct

Subtask #2
0 / 40.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1614 ms 19508 KB Output is correct
2 Correct 70 ms 19836 KB Output is correct
3 Correct 1549 ms 19556 KB Output is correct
4 Correct 61 ms 19796 KB Output is correct
5 Correct 70 ms 19696 KB Output is correct
6 Correct 63 ms 19540 KB Output is correct
7 Correct 74 ms 19648 KB Output is correct
8 Correct 64 ms 19536 KB Output is correct
9 Correct 66 ms 19536 KB Output is correct
10 Correct 57 ms 19860 KB Output is correct
11 Correct 62 ms 20052 KB Output is correct
12 Correct 58 ms 20060 KB Output is correct
13 Correct 59 ms 19804 KB Output is correct
14 Correct 61 ms 20060 KB Output is correct
15 Correct 59 ms 19952 KB Output is correct
16 Correct 32 ms 17844 KB Output is correct
17 Correct 62 ms 19584 KB Output is correct
18 Correct 56 ms 17508 KB Output is correct
19 Correct 2 ms 12632 KB Output is correct
20 Correct 2 ms 12636 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 30716 KB Output is correct
2 Correct 304 ms 29584 KB Output is correct
3 Correct 298 ms 29264 KB Output is correct
4 Correct 283 ms 28724 KB Output is correct
5 Correct 295 ms 31436 KB Output is correct
6 Correct 289 ms 32076 KB Output is correct
7 Correct 310 ms 32848 KB Output is correct
8 Correct 282 ms 30364 KB Output is correct
9 Correct 299 ms 29396 KB Output is correct
10 Correct 295 ms 29008 KB Output is correct
11 Correct 302 ms 29268 KB Output is correct
12 Correct 288 ms 27928 KB Output is correct
13 Correct 323 ms 28324 KB Output is correct
14 Correct 295 ms 30952 KB Output is correct
15 Correct 303 ms 28652 KB Output is correct
16 Correct 2 ms 12636 KB Output is correct
17 Correct 278 ms 27804 KB Output is correct
18 Correct 272 ms 27664 KB Output is correct
19 Correct 2 ms 12636 KB Output is correct
20 Correct 2 ms 12636 KB Output is correct
21 Execution timed out 3027 ms 31056 KB Time limit exceeded
22 Halted 0 ms 0 KB -