Submission #1128926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128926		ByeWorld	Martian DNA (BOI18_dna)	C++20	100 / 100	31 ms	4680 KiB

dna

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 3e5+10;
const int MAXA = 1e6;
const int INF = 1e18+10;
const int MOD = 1e9+7;
const int LOG = 32;
const ld EPS = 1e-12;

int n, k, r, a[MAXN], mn[MAXN], tot[MAXN];
int ans = INF;

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> k >> r;
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=r; i++){
        int id; cin >> id; cin >> mn[id];
    }
    int cnt = k-r, en = 0;
    for(int i=1; i<=n; i++){
        en = i;
        tot[a[i]]++; 
        if(tot[a[i]] == mn[a[i]]) cnt++;
        if(cnt==k) break;
    }
    if(cnt != k){
        cout << "impossible\n"; exit(0);
    }
    // cout << en << " en\n";
    ans = en;

    for(int i=1; i<=n; i++){
        tot[a[i]]--; // delete i
        while(en<=n && tot[a[i]] < mn[a[i]]){
            en++; tot[a[en]]++;
        }
        if(en == n+1) break;

        ans = min(ans, en-i);
    }

    cout << ans << '\n';
}

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