Submission #1287565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287565		Hamed_Ghaffari	Martian DNA (BOI18_dna)	C++20	100 / 100	112 ms	16408 KiB

dna

#include <bits/stdc++.h>
using namespace std;

#define SZ(x) int(x.size())

const int MXN = 2e5+5;

int n, k, r, a[MXN], b[MXN];
vector<int> vec[MXN];

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> k >> r;
    for(int i=0; i<n; i++) cin >> a[i], vec[a[i]].push_back(i);
    int mx = 0;
    while(r--) {
        int x, y;
        cin >> x >> y;
        if(y>SZ(vec[x])) {
            cout << "impossible\n";
            return 0;
        }
        mx = max(mx, vec[x][y-1]);
        b[x] = y;
    }
    int ans = n;
    set<int> st;
    for(int i=0; i<n; i++) {
        if(b[a[i]]) {
            int pos = lower_bound(vec[a[i]].begin(), vec[a[i]].end(), i)-vec[a[i]].begin();
            if(pos-b[a[i]]>=0) st.erase(vec[a[i]][pos-b[a[i]]]);
            if(pos-b[a[i]]+1>=0) st.insert(vec[a[i]][pos-b[a[i]]+1]);
        }
        if(i>=mx) ans = min(ans, i - (*st.begin()) + 1);
    }
    cout << ans << '\n';
    return 0;
}

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