oj.uz

Submission #1022021

# Submission time Handle Problem Language Result Execution time Memory
1022021 2024-07-13T09:04:20 Z vjudge1 Martian DNA (BOI18_dna) C++
0 / 100
 54 ms 4908 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int MAX_N = 200005;

void solve() {
    int n, k, R;
    cin >> n >> k >> R;
    vector<int>req(k, 0);
    int a[n];
    for(int i=0; i<n; ++i) cin >> a[i];
    for(int i=0; i<R; ++i) {
        int b, q;
        cin >> b >> q;
        req[b] = q;
    }
    int need = R, l = 0, r = 0, ans = n+1;
    vector<int>cnt(k, 0);
    ++cnt[a[0]];
    if(req[a[0]] == 1) --need;
    while(r < n) {
        while(r != l) {
            if((cnt[a[l]]-1) >= req[a[l]]) {
                ++l;
                --cnt[a[l]];
            } else break;
        }
        if(!need) ans = min(ans, r-l+1);
        if(r == n-1) break;
        ++r, ++cnt[a[r]];
        if(cnt[a[r]] == req[a[r]]) --need;
    }
    if(ans == n+1) cout << "impossible" << endl;
    else cout << ans << endl;
}

signed main() {
    int t = 1;
    while(t--) solve();

    return 0;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 2140 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 4908 KB Output isn't correct
2 Halted 0 ms 0 KB -