Submission #554931

#	Time	Username	Problem	Language	Result	Execution time	Memory
554931		new_acc	Martian DNA (BOI18_dna)	C++14	0 / 100	97 ms	6040 KiB

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