Submission #1022163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022163		vjudge1	Martian DNA (BOI18_dna)	C++17	100 / 100	154 ms	17236 KiB

dna

#include <iostream>
//#include <bits/stdc++.h>
#include <iomanip>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<ll> vi;
typedef vector<bool> vb;
const ll mm = 1000000007;
const int maxn = 2e5 + 1;



int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    ll n, k, r; cin >> n >> k >> r;
    vi a(n), kb(n);
    map<ll, ll> g;
    vb b(r);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < r; i++) {
        ll x, y; cin >> x >> y;
        g[x] = y;
    }

    ll rez = n+1, brojdobrih=0;
    ll st = 0,end=0;

    ll p = a[end];
    kb[p]++;
    if (kb[p] == g[p]) {
        brojdobrih++;
    }
    

    while (st<n) {
        /*
        cout << "STANJE" << endl;
        cout << "st i end:" << st << " i " << end << endl;
        cout << "brojdobrih: " << brojdobrih << endl;
        for (auto x : kb) cout << x << " ";
        cout << endl << endl;*/

        if (brojdobrih < r) {
            if (end == n - 1) { //
                st = n;
            }
            else {
                end++;
                ll p = a[end];
                kb[p]++;
                if (kb[p] == g[p]) {
                    brojdobrih++;
                }
            }

        }
        else {
            //cout << "jupi!" << endl;
            rez = min(rez, end - st + 1);

            ll p = a[st];
            kb[p]--;
            if (g[p] == 0) {
                //:)
            }
            else if(kb[p]<g[p]){
                brojdobrih--;
            }
            st++;

        }
    


    }

    if (rez == n + 1) cout << "impossible" << endl;
    else cout << rez << endl;


    return 0;

}

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