oj.uz

Submission #933473

# Submission time Handle Problem Language Result Execution time Memory
933473 2024-02-25T17:42:28 Z sleepntsheep Martian DNA (BOI18_dna) C
0 / 100
 160 ms 24116 KB 
#include<stdio.h>
unsigned X=12345;int rand_(){return(X*=3)>>1;}
#define N 400002
int n,k,rn,a[N],ii[N],ff[N];
long long A[N];int B[N],L[N],R[N],alc;

int t0(long long x){int p=++alc;A[p]=x;B[p]=rand_();return p;}
void tsp(int v,int*l,int*r,long long k) {
    if(!v){*l=*r=0;return;}
    if(A[v]>k)tsp(L[v],l,L+v,k),*r=v;
    else tsp(R[v],R+v,r,k),*l=v;
}
void tme(int*v,int l,int r) {
    if(!l||!r){*v=l^r;return;}
    if(B[l]<B[r]) tme(L+r,l,L[r]), *v=r;
    else tme(R+l,R[l],r), *v=l;
}
long long tmn(int v){
    while(L[v])v=L[v];
    return A[v];
}

int t;
void add(int i,int k)
{
    if(!ii[i])return;
    int p1,p2,p3,p4,p5,p6,p7,p8;
    tsp(t,&p1,&p2,200001ll*ff[i]+i);
    tsp(p1,&p3,&p4,200001ll*ff[i]+i-1);
    long long tt=A[p4]+=200001*k;
    ff[i]+=k;
    tme(&t,p3,p2);
    tsp(t,&p5,&p6,A[p4]);
    tme(&p7,p5,t0(tt));
    tme(&t,p7,p6);
}

int main()
{
    scanf("%d%d%d",&n,&k,&rn);
    for(int i=0;i<n;++i)scanf("%d",a+i);
    for(int b,q;rn--;)
        scanf("%d%d",&b,&q),tme(&t,t,t0(200001ll*-q+b)),ii[b]=1,ff[b]=-q;
    int l=0,r=0,z=1e9;
    while(l<n)
    {
        while(r<=l)add(a[r++],1);
        while(tmn(t)<0&&r<n)add(a[r++],1);
        if(tmn(t)>=0&&z>r-l)z=r-l;
        add(a[l++],-1);
    }
    if(z==1e9)puts("impossible");else printf("%d",z);
}

Compilation message

dna.c: In function 'add':
dna.c:27:30: warning: unused variable 'p8' [-Wunused-variable]
   27 |     int p1,p2,p3,p4,p5,p6,p7,p8;
      |                              ^~
dna.c: In function 'main':
dna.c:40:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d%d%d",&n,&k,&rn);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~
dna.c:41:25: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     for(int i=0;i<n;++i)scanf("%d",a+i);
      |                         ^~~~~~~~~~~~~~~
dna.c:43:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%d%d",&b,&q),tme(&t,t,t0(200001ll*-q+b)),ii[b]=1,ff[b]=-q;
      |         ^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Incorrect 1 ms 8536 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Incorrect 4 ms 8540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 146 ms 12132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

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