Submission #933475

#	Time	Username	Problem	Language	Result	Execution time	Memory
933475		sleepntsheep	Martian DNA (BOI18_dna)	C++17	0 / 100	190 ms	16548 KiB

dna

#include<stdio.h>
unsigned X=12345;int rand_(){return(X*=3)>>1;}
#define N 200002
int n,k,rn,a[N],ii[N],ff[N];
#define M 1000000
long long A[M];int B[M],L[M],R[M],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];
}

const long long AA=5e12;
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,AA*ff[i]+i);
    tsp(p1,&p3,&p4,AA*ff[i]+i-1);
    long long tt=A[p4]+=AA*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(AA*-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 (stderr)

dna.cpp: In function 'void add(int, int)':
dna.cpp:29:30: warning: unused variable 'p8' [-Wunused-variable]
   29 |     int p1,p2,p3,p4,p5,p6,p7,p8;
      |                              ^~
dna.cpp: In function 'int main()':
dna.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     scanf("%d%d%d",&n,&k,&rn);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
dna.cpp:43:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     for(int i=0;i<n;++i)scanf("%d",a+i);
      |                         ~~~~~^~~~~~~~~~
dna.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         scanf("%d%d",&b,&q),tme(&t,t,t0(AA*-q+b)),ii[b]=1,ff[b]=-q;
      |         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 16
• Subtask 2: 0 / 24
• Subtask 3: 0 / 28
• Subtask 4: 0 / 32