#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
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;
| ^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
192 ms |
16980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
178 ms |
28500 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
