Submission #554931

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
554931	2022-04-29T16:04:38 Z	new_acc	Martian DNA (BOI18_dna)	C++14	0 / 100	97 ms	6040 KB

dna

#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e6+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e13;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
int t[N],lim[N],il[N],g[N];
ull pot[N];
void solve(){
    int n,k,m;
    cin>>n>>k>>m;
    for(int i=1;i<=n;i++) cin>>t[i];
    pot[0]=1;
    for(int i=1;i<=m;i++) pot[i]=pot[i-1]*p2;
    for(int i=0;i<k;i++) lim[i]=INFi;
    for(int a,b,i=1;i<=m;i++){
        cin>>a>>b;
        lim[a]=b,g[a]=i;
    }
    int res=-1,wsk=1;
    ull curr=0,total=0;
    for(int i=1;i<=m;i++) total+=pot[i];
    for(int i=1;i<=n;i++){
        wsk=max(wsk,i); 
        while(wsk<=n and curr!=total){
            il[t[wsk]]++;
            if(lim[t[wsk]]==il[t[wsk]]) curr+=pot[g[t[wsk]]];
            wsk++;
        }
        if(wsk<=n) res=(res==-1?wsk-i:min(res,wsk-i));
        il[t[i]]--; 
        if(lim[t[i]]==il[t[i]]+1) curr-=pot[g[t[i]]];
    }
    if(res==-1) cout<<"impossible\n";
    else cout<<res<<"\n";
}
int main(){
    int tt=1;
    //cin>>tt;
    while(tt--) solve();
}

Subtask #1

0 / 16.0

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

Subtask #2

0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	308 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	2 ms	324 KB	Output is correct
4	Correct	1 ms	320 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Incorrect	1 ms	340 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #3

0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	1480 KB	Output is correct
2	Correct	29 ms	1492 KB	Output is correct
3	Correct	30 ms	1488 KB	Output is correct
4	Correct	29 ms	1520 KB	Output is correct
5	Correct	54 ms	2876 KB	Output is correct
6	Incorrect	31 ms	1504 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #4

0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	85 ms	4388 KB	Output is correct
2	Correct	77 ms	3780 KB	Output is correct
3	Correct	67 ms	3192 KB	Output is correct
4	Correct	30 ms	1484 KB	Output is correct
5	Correct	96 ms	4948 KB	Output is correct
6	Correct	97 ms	6040 KB	Output is correct
7	Correct	51 ms	2216 KB	Output is correct
8	Correct	55 ms	2528 KB	Output is correct
9	Correct	28 ms	1432 KB	Output is correct
10	Correct	28 ms	1468 KB	Output is correct
11	Correct	29 ms	1444 KB	Output is correct
12	Correct	29 ms	1492 KB	Output is correct
13	Correct	51 ms	2892 KB	Output is correct
14	Incorrect	28 ms	1500 KB	Output isn't correct
15	Halted	0 ms	0 KB	-