Submission #933472

#	Time	Username	Problem	Language	Result	Execution time	Memory
933472		sleepntsheep	Martian DNA (BOI18_dna)	C11	0 / 100	192 ms	28500 KiB

dna

#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);
        printf(" : %d %d %lld\n",l,r,tmn(t));
        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 (stderr)

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
• Subtask 2: 0 / 24
• Subtask 3: 0 / 28
• Subtask 4: 0 / 32