Submission #1290937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290937		a__turki	Martian DNA (BOI18_dna)	C++20	100 / 100	360 ms	16268 KiB

dna

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define int long long
#define mod 1000000007
#define ld long double
#define all(x) (x).begin() , (x).end()
#define pb push_back
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    ll tt=1;
    // cin >> tt;
    while(tt--){
        ll n,k,r,en=0;
        cin >> n >> k >> r;
        vector<ll> a(n),f(k,0);
        vector<array<ll,2>> b(r);
        map<ll,ll> m;
        for(int i=0; i<n; i++) cin >> a[i],f[a[i]]++;
        for(int i=0; i<r; i++) cin >> b[i][0] >> b[i][1],m[b[i][0]]=b[i][1];
        ll h=r,ans=n+1;
        for(int st=0; st<n; st++){
            while(h>0 && en<n){
                m[a[en]]--;
                if(m[a[en]]==0) h--;
                en++;
            }
            if(h==0) ans=min(ans,en-st);
            m[a[st]]++;
            if(m[a[st]]==1) h++;
        }
        if(ans==n+1) cout << "impossible";
        else cout << ans;
    }
    return 0;
    }

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