Submission #733510

#	Time	Username	Problem	Language	Result	Execution time	Memory
733510		rahulverma	Martian DNA (BOI18_dna)	Java	100 / 100	1668 ms	38176 KiB

dna

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);
		
		
	}

}

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