Submission #933477

#	Time	Username	Problem	Language	Result	Execution time	Memory
933477		sleepntsheep	Martian DNA (BOI18_dna)	C++17	100 / 100	184 ms	9268 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];
#include<set>
#include<utility>
std::set<std::pair<int,int>>ss;

int t;
void add(int i,int k)
{
    if(!ii[i])return;
    ss.erase({ff[i],i});
    ss.insert({ff[i]+=k,i});
}

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),ss.insert({-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(ss.begin()->first<0&&r<n)add(a[r++],1);
        if(ss.begin()->first>=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 'int main()':
dna.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf("%d%d%d",&n,&k,&rn);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
dna.cpp:20:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     for(int i=0;i<n;++i)scanf("%d",a+i);
      |                         ~~~~~^~~~~~~~~~
dna.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf("%d%d",&b,&q),ss.insert({-q,b}),ii[b]=1,ff[b]=-q;
      |         ~~~~~^~~~~~~~~~~~~~

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