import java.io.*;
import java.util.*;
class dna {
public static void main(String[] args) {
// TODO Auto-generated method stub
// two pointers
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int k = s.nextInt();
int r = s.nextInt();
int[] freq = new int[k+5];
int[] req = new int[k+5];
int[] arr = new int[n];
for(int i = 0; i < n; i++) {
arr[i] = s.nextInt();
freq[arr[i]]++;
}
for(int i = 0; i < r; i++) {
int v1 = s.nextInt();
int v2 = s.nextInt();
req[v1] += v2;
}
for(int i = 0; i < k + 5; i++) {
if(freq[i] < req[i]) {
System.out.println("impossible");
return;
}
}
int left = 0;
int right = n;
while(left < right) {
int mid = left + (right - left)/2;
boolean works = false;
int[] curFreq = new int[k+5];
for(int i = 0; i < mid; i++) {
curFreq[arr[i]]++;
}
HashSet<Integer> invalid = new HashSet<>();
for(int i = 0; i < k+5; i++) {
if(curFreq[i] < req[i]) {
invalid.add(i);
}
}
if(invalid.size() == 0) works = true;
else {
for(int i = mid; i < n; i++) {
curFreq[arr[i]]++;
if(invalid.contains(arr[i]) && curFreq[arr[i]] >= req[arr[i]]) {
invalid.remove(arr[i]);
}
curFreq[arr[i-mid]]--;
if(curFreq[arr[i-mid]] < req[arr[i-mid]]) {
invalid.add(arr[i-mid]);
}
if(invalid.size() == 0) {
works = true;
break;
}
}
}
if(works) {
right = mid;
}
else {
left = mid + 1;
}
}
System.out.println(left);
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
121 ms |
10784 KB |
Output is correct |
| 2 |
Correct |
136 ms |
10828 KB |
Output is correct |
| 3 |
Correct |
124 ms |
10912 KB |
Output is correct |
| 4 |
Correct |
127 ms |
10816 KB |
Output is correct |
| 5 |
Correct |
120 ms |
10760 KB |
Output is correct |
| 6 |
Correct |
97 ms |
10228 KB |
Output is correct |
| 7 |
Correct |
120 ms |
10996 KB |
Output is correct |
| 8 |
Correct |
115 ms |
10284 KB |
Output is correct |
| 9 |
Correct |
124 ms |
10916 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
358 ms |
15376 KB |
Output is correct |
| 2 |
Correct |
431 ms |
17052 KB |
Output is correct |
| 3 |
Correct |
334 ms |
15928 KB |
Output is correct |
| 4 |
Correct |
341 ms |
15876 KB |
Output is correct |
| 5 |
Correct |
360 ms |
15692 KB |
Output is correct |
| 6 |
Correct |
350 ms |
15364 KB |
Output is correct |
| 7 |
Correct |
110 ms |
10496 KB |
Output is correct |
| 8 |
Correct |
119 ms |
10856 KB |
Output is correct |
| 9 |
Correct |
126 ms |
10816 KB |
Output is correct |
| 10 |
Correct |
122 ms |
10916 KB |
Output is correct |
| 11 |
Correct |
120 ms |
10748 KB |
Output is correct |
| 12 |
Correct |
93 ms |
10416 KB |
Output is correct |
| 13 |
Correct |
119 ms |
10772 KB |
Output is correct |
| 14 |
Correct |
130 ms |
10368 KB |
Output is correct |
| 15 |
Correct |
122 ms |
10664 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
827 ms |
19760 KB |
Output is correct |
| 2 |
Correct |
791 ms |
19984 KB |
Output is correct |
| 3 |
Correct |
782 ms |
20156 KB |
Output is correct |
| 4 |
Correct |
781 ms |
19980 KB |
Output is correct |
| 5 |
Correct |
737 ms |
24404 KB |
Output is correct |
| 6 |
Correct |
724 ms |
20076 KB |
Output is correct |
| 7 |
Correct |
588 ms |
19612 KB |
Output is correct |
| 8 |
Correct |
867 ms |
24952 KB |
Output is correct |
| 9 |
Correct |
729 ms |
20100 KB |
Output is correct |
| 10 |
Correct |
822 ms |
19928 KB |
Output is correct |
| 11 |
Correct |
352 ms |
15288 KB |
Output is correct |
| 12 |
Correct |
412 ms |
16772 KB |
Output is correct |
| 13 |
Correct |
356 ms |
15744 KB |
Output is correct |
| 14 |
Correct |
347 ms |
15940 KB |
Output is correct |
| 15 |
Correct |
364 ms |
15884 KB |
Output is correct |
| 16 |
Correct |
347 ms |
15152 KB |
Output is correct |
| 17 |
Correct |
115 ms |
10516 KB |
Output is correct |
| 18 |
Correct |
121 ms |
11068 KB |
Output is correct |
| 19 |
Correct |
124 ms |
10956 KB |
Output is correct |
| 20 |
Correct |
124 ms |
10776 KB |
Output is correct |
| 21 |
Correct |
116 ms |
10832 KB |
Output is correct |
| 22 |
Correct |
95 ms |
10156 KB |
Output is correct |
| 23 |
Correct |
116 ms |
10728 KB |
Output is correct |
| 24 |
Correct |
108 ms |
10476 KB |
Output is correct |
| 25 |
Correct |
117 ms |
10912 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1055 ms |
27180 KB |
Output is correct |
| 2 |
Correct |
1044 ms |
25232 KB |
Output is correct |
| 3 |
Correct |
896 ms |
23948 KB |
Output is correct |
| 4 |
Correct |
674 ms |
19276 KB |
Output is correct |
| 5 |
Correct |
696 ms |
21744 KB |
Output is correct |
| 6 |
Correct |
1668 ms |
38176 KB |
Output is correct |
| 7 |
Correct |
867 ms |
21376 KB |
Output is correct |
| 8 |
Correct |
933 ms |
22324 KB |
Output is correct |
| 9 |
Correct |
786 ms |
20016 KB |
Output is correct |
| 10 |
Correct |
795 ms |
19964 KB |
Output is correct |
| 11 |
Correct |
810 ms |
19884 KB |
Output is correct |
| 12 |
Correct |
777 ms |
19948 KB |
Output is correct |
| 13 |
Correct |
731 ms |
23968 KB |
Output is correct |
| 14 |
Correct |
741 ms |
19952 KB |
Output is correct |
| 15 |
Correct |
579 ms |
19404 KB |
Output is correct |
| 16 |
Correct |
867 ms |
24876 KB |
Output is correct |
| 17 |
Correct |
727 ms |
20072 KB |
Output is correct |
| 18 |
Correct |
850 ms |
19900 KB |
Output is correct |
| 19 |
Correct |
348 ms |
15188 KB |
Output is correct |
| 20 |
Correct |
426 ms |
16780 KB |
Output is correct |
| 21 |
Correct |
348 ms |
15664 KB |
Output is correct |
| 22 |
Correct |
374 ms |
15796 KB |
Output is correct |
| 23 |
Correct |
353 ms |
15700 KB |
Output is correct |
| 24 |
Correct |
344 ms |
15232 KB |
Output is correct |
| 25 |
Correct |
107 ms |
10372 KB |
Output is correct |
| 26 |
Correct |
114 ms |
10848 KB |
Output is correct |
| 27 |
Correct |
112 ms |
10936 KB |
Output is correct |
| 28 |
Correct |
128 ms |
10760 KB |
Output is correct |
| 29 |
Correct |
118 ms |
10912 KB |
Output is correct |
| 30 |
Correct |
96 ms |
10128 KB |
Output is correct |
| 31 |
Correct |
123 ms |
10852 KB |
Output is correct |
| 32 |
Correct |
106 ms |
10572 KB |
Output is correct |
| 33 |
Correct |
117 ms |
11100 KB |
Output is correct |
