Source Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class Codeforces {

    static FastReader input = new FastReader();
    static final int INF = (int) 1e9 + 20;
    static long xe, ye, d;
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        int t = input.nextInt();
        for(int z=0; z<t; z++){
            int n = input.nextInt();
            int k = input.nextInt();
            int[] freq = new int[n+1];
            int[] arr = new int[n];
            boolean valid = true;
            for(int i=0; i<n; i++){
                arr[i] = input.nextInt();
                freq[arr[i]]++;
            }
            ArrayList<Pair> queries = new ArrayList<>();
            for(int i=0; i<k; i++){
                Pair p = new Pair(input.nextInt(), input.nextInt());
                if(i == 0){
                    queries.add(p);
                }
                if(i>0){
                    if(queries.get(queries.size()-1).first == p.first){
                        p.second = queries.get(queries.size()-1).second + p.second;
                        queries.set(queries.size()-1, p);
                    }
                    else{
                       queries.add(p); 
                    }
                    if(queries.size() > 1 && queries.get(queries.size()-2).first > queries.get(queries.size()-1).first){
                        valid = false;
                    }
                }
            }
            int ind = 0;
            int currentCount = 0;
            for(int i=0; i<arr.length; i++){
                if(ind >= queries.size()){
                    valid = false;
                    break;
                }
                int x = queries.get(ind).first;
                int count = queries.get(ind).second;
                if(currentCount == count && arr[i] == x){
                    currentCount = 0;
                    ind++;
                }
                else if(currentCount == count && arr[i] != x){
                    if(ind+1 < queries.size() && queries.get(ind+1).first == arr[i]){
                        if(freq[queries.get(ind+1).first] > queries.get(ind+1).second){
                            freq[queries.get(ind+1).first]--;
                            continue;
                        }
                        else if(freq[queries.get(ind+1).first] == queries.get(ind+1).second){
                            ind++;
                            currentCount = 1;
                        }
                    }
                    else{
                        continue;
                    }
                }
                else if(currentCount< count && arr[i] > x){
                    valid = false;
                    break;
                }
                else if(arr[i] == x){
                    currentCount++;
                } 
            }
            if(currentCount < queries.get(ind).second || ind != queries.size()-1){
                valid = false;
            }
            if(valid){
                System.out.println("yes");
            }
            else{
                System.out.println("no");
            }
        }
    }
    public static class Pair{
        int first;
        int second;
        public Pair(int first, int second){
            this.first= first;
            this.second = second;
        }
    }

    static class FastReader {
 
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader() {
            /*try {
             br = new BufferedReader(new FileReader(new File("travel_restrictions_validation_input.txt")));
             } catch (FileNotFoundException e) {
             e.printStackTrace();
             }*/
            br = new BufferedReader(new InputStreamReader(System.in));
        }
 
        String next() throws IOException {
            while (st == null || !st.hasMoreElements()) {
                st = new StringTokenizer(br.readLine());
            }
            return st.nextToken();
        }
 
        int nextInt() throws NumberFormatException, IOException {
            return Integer.parseInt(next());
        }
 
        long nextLong() throws NumberFormatException, IOException {
            return Long.parseLong(next());
        }
 
        double nextDouble() throws NumberFormatException, IOException {
            return Double.parseDouble(next());
        }
 
        String nextLine() throws IOException {
            String str = "";
            str = br.readLine();
            return str;
        }
 
        boolean hasNext() throws IOException {
            return br.ready();
        }
    }
}
Copy
Sorted Array Partitioning Catwoman
Java 11
137 ms
15.7 MB
Runtime Error