Submission #388416

#	Time	Username	Problem	Language	Result	Execution time	Memory
388416		leaked	Martian DNA (BOI18_dna)	C++14	100 / 100	245 ms	25164 KiB

dna

#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define vec vector
#define pb push_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
typedef unsigned long long ull;
auto rnd=bind(uniform_int_distribution<long long>(1,1e18),mt19937(time(0)));

signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,k,q;
    cin>>n>>k>>q;
    vec<pii>need(q);
    vec<int>a(n);
    map<int,int>mp;
    int cr=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(!mp.count(a[i])){
            mp[a[i]]=cr++;
        }
        a[i]=mp[a[i]];
    }
    for(auto &z : need){
        cin>>z.f>>z.s;
        if(!mp.count(z.f)) mp[z.f]=cr++;
        z.f=mp[z.f];
    }
    vec<int>pos(n,-1);
    vec<vec<int>>vc(cr,vec<int>());
    vec<int>last(sz(mp),-1);
    vec<int>nxt(cr,-1);
    for(auto &z : need) nxt[z.f]=z.s;
    for(int i=0;i<n;i++){
        pos[i]=sz(vc[a[i]]);
        vc[a[i]].pb(i);
    }
    for(auto &z : vc) reverse(all(z));
    int ans=2e9;
    int mx=-1;
    for(auto &z : need){
        if(sz(vc[z.f])<z.s){
            cout<<"impossible";
            return 0;
        }
        mx=max(mx,vc[z.f][sz(vc[z.f])-z.s]);
    }
    ans=min(ans,mx+1);
    for(int i=0;i<n;i++){
        int clr=a[i];
        vc[clr].pop_back();
        if(nxt[clr]!=-1){
            if(sz(vc[clr])<nxt[clr]) break;
            mx=max(mx,vc[clr][sz(vc[clr])-nxt[clr]]);
        }
        ans=min(ans,mx-i);
//        cerr<<i<<' '<<mx<<endl;
    }
    if(ans==2e9) cout<<"impossible";
    else cout<<ans;
    return 0;
}

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