#include <bits/stdc++.h>
using namespace std;
int states[200005];
map<int, pair<int, int>> req;
set<int> completed;
map<int, int> have;
int n, k, r;
bool move(int &idx) {
if (completed.size() == r) return true;
while (completed.size() < r) {
idx++;
if (idx > n) return false;
have[states[idx]]++;
if (have[states[idx]] == req[states[idx]].first) {
completed.insert(req[states[idx]].second);
}
}
return true;
}
int main() {
cin >> n >> k >> r;
for (int i = 1; i <= n; i++) cin >> states[i];
for (int i = 0; i < r; i++) {
int b, q; cin >> b >> q;
req[b] = {q, i};
}
int idx = 0;
bool able = move(idx);
if (!able) {
cout << "impossible";
return 0;
}
int l = 1;
int ans = (idx - l + 1);
// cout << l << " " << idx << endl;
while (l < n) {
if (req[states[l]].first == have[states[l]]) {
completed.erase(req[states[l]].second);
}
have[states[l]]--;
l++;
able = move(idx);
if (!able) break;
ans = min(ans, idx - l + 1);
}
cout << ans;
}
Compilation message
dna.cpp: In function 'bool move(int&)':
dna.cpp:13:26: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
13 | if (completed.size() == r) return true;
| ~~~~~~~~~~~~~~~~~^~~~
dna.cpp:15:29: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
15 | while (completed.size() < r) {
| ~~~~~~~~~~~~~~~~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
308 KB |
Output is correct |
| 8 |
Correct |
1 ms |
308 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
3 ms |
596 KB |
Output is correct |
| 4 |
Correct |
4 ms |
708 KB |
Output is correct |
| 5 |
Correct |
3 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
316 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
308 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
38 ms |
1120 KB |
Output is correct |
| 2 |
Correct |
36 ms |
1432 KB |
Output is correct |
| 3 |
Correct |
50 ms |
1456 KB |
Output is correct |
| 4 |
Correct |
47 ms |
1584 KB |
Output is correct |
| 5 |
Correct |
238 ms |
10900 KB |
Output is correct |
| 6 |
Correct |
32 ms |
1364 KB |
Output is correct |
| 7 |
Correct |
48 ms |
1564 KB |
Output is correct |
| 8 |
Correct |
359 ms |
24248 KB |
Output is correct |
| 9 |
Correct |
138 ms |
2896 KB |
Output is correct |
| 10 |
Correct |
40 ms |
1440 KB |
Output is correct |
| 11 |
Correct |
2 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
3 ms |
596 KB |
Output is correct |
| 14 |
Correct |
4 ms |
724 KB |
Output is correct |
| 15 |
Correct |
4 ms |
468 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
316 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
312 KB |
Output is correct |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Correct |
1 ms |
212 KB |
Output is correct |
| 23 |
Correct |
1 ms |
212 KB |
Output is correct |
| 24 |
Correct |
1 ms |
212 KB |
Output is correct |
| 25 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
479 ms |
13716 KB |
Output is correct |
| 2 |
Correct |
455 ms |
12124 KB |
Output is correct |
| 3 |
Correct |
253 ms |
9764 KB |
Output is correct |
| 4 |
Correct |
37 ms |
1464 KB |
Output is correct |
| 5 |
Correct |
335 ms |
14120 KB |
Output is correct |
| 6 |
Correct |
646 ms |
27608 KB |
Output is correct |
| 7 |
Correct |
120 ms |
3260 KB |
Output is correct |
| 8 |
Correct |
181 ms |
5128 KB |
Output is correct |
| 9 |
Correct |
39 ms |
1456 KB |
Output is correct |
| 10 |
Correct |
42 ms |
1456 KB |
Output is correct |
| 11 |
Correct |
52 ms |
1492 KB |
Output is correct |
| 12 |
Correct |
46 ms |
1404 KB |
Output is correct |
| 13 |
Correct |
231 ms |
11004 KB |
Output is correct |
| 14 |
Correct |
32 ms |
1432 KB |
Output is correct |
| 15 |
Correct |
46 ms |
1612 KB |
Output is correct |
| 16 |
Correct |
350 ms |
24228 KB |
Output is correct |
| 17 |
Correct |
140 ms |
2896 KB |
Output is correct |
| 18 |
Correct |
46 ms |
1396 KB |
Output is correct |
| 19 |
Correct |
1 ms |
212 KB |
Output is correct |
| 20 |
Correct |
2 ms |
340 KB |
Output is correct |
| 21 |
Correct |
3 ms |
596 KB |
Output is correct |
| 22 |
Correct |
4 ms |
680 KB |
Output is correct |
| 23 |
Correct |
3 ms |
468 KB |
Output is correct |
| 24 |
Correct |
1 ms |
340 KB |
Output is correct |
| 25 |
Correct |
1 ms |
212 KB |
Output is correct |
| 26 |
Correct |
1 ms |
268 KB |
Output is correct |
| 27 |
Correct |
1 ms |
212 KB |
Output is correct |
| 28 |
Correct |
1 ms |
212 KB |
Output is correct |
| 29 |
Correct |
1 ms |
312 KB |
Output is correct |
| 30 |
Correct |
1 ms |
212 KB |
Output is correct |
| 31 |
Correct |
1 ms |
212 KB |
Output is correct |
| 32 |
Correct |
1 ms |
312 KB |
Output is correct |
| 33 |
Correct |
1 ms |
212 KB |
Output is correct |
