Submission #1116904

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1116904	2024-11-22T14:33:47 Z	njoop	Martian DNA (BOI18_dna)	C++14	0 / 100	36 ms	5572 KB

dna

#include <bits/stdc++.h>
 
using namespace std;
 
int n, k, r, req[300010], amt[300010], qu, ans = 1e9, p1 = 0, p2 = 0;
vector<int> dna;

void add(int type) {
    if(req[type] == 0) return;
    if(req[type] == amt[type]+1) {
        qu++;
    }
    amt[type]++;
}
 
void del(int type) {
    if(req[type] == 0) return;
    if(req[type] == amt[type]) {
        qu--;
    }
    amt[type]--;
}
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k >> r;
    for(int i=1; i<=n; i++) {
        int in;
        cin >> in;
        dna.push_back(in);
    }
    for(int i=1; i<=r; i++) {
        int b, q;
        cin >> b >> q;
        req[b] = q;
    }
    while(p2 < n) {
        if(qu == r && p1 < p2) {
            ans = min(ans, p2-p1);
            del(dna[p1]);
            p1++;
        } else {
            add(dna[p2]);
            p2++;
        }
    }
    if(ans == 1e9) {
        cout << "impossible";
    } else {
        cout << ans;
    }
    return 0;
}

Subtask #1

0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2384 KB	Output is correct
2	Correct	1 ms	2552 KB	Output is correct
3	Incorrect	1 ms	2384 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2

0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2384 KB	Output is correct
2	Correct	1 ms	2384 KB	Output is correct
3	Correct	2 ms	2552 KB	Output is correct
4	Correct	1 ms	2384 KB	Output is correct
5	Correct	1 ms	2384 KB	Output is correct
6	Correct	1 ms	2560 KB	Output is correct
7	Correct	1 ms	2384 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Incorrect	1 ms	2384 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #3

0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	3788 KB	Output is correct
2	Correct	11 ms	3788 KB	Output is correct
3	Correct	13 ms	3800 KB	Output is correct
4	Correct	10 ms	3788 KB	Output is correct
5	Correct	13 ms	4556 KB	Output is correct
6	Incorrect	10 ms	3748 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #4

0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	5324 KB	Output is correct
2	Correct	19 ms	5084 KB	Output is correct
3	Correct	16 ms	4812 KB	Output is correct
4	Correct	9 ms	3596 KB	Output is correct
5	Correct	36 ms	5572 KB	Output is correct
6	Correct	29 ms	5572 KB	Output is correct
7	Correct	13 ms	4300 KB	Output is correct
8	Correct	16 ms	4516 KB	Output is correct
9	Correct	10 ms	3956 KB	Output is correct
10	Correct	11 ms	3788 KB	Output is correct
11	Correct	12 ms	3788 KB	Output is correct
12	Correct	12 ms	3788 KB	Output is correct
13	Correct	15 ms	4460 KB	Output is correct
14	Incorrect	10 ms	3788 KB	Output isn't correct
15	Halted	0 ms	0 KB	-