Source Code
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
void setIO(string name = "") { // see /general/fast-io
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
}

int main(){
	//setIO();
	int t;
	cin>>t;
	while(t--){
		int n,k;
		cin>>n>>k;
		vector<int> v(n);
		map<int,int> mp,mp0;
		for(int i = 0; i < n ; i++){
			cin>>v[i];
			mp[v[i]]++;
		}
		vector<pair<int,int>> w;
		int a,b;
		bool stp = false;
		for(int i = 0; i < k ; i++){
			cin>>a>>b;
			w.push_back({a,b});
			mp0[a]+=b;
			if(mp0[a]>mp[a]){
				stp = true;
			}
			if(!w.empty() && a < w[w.size()-1].first){
				stp = true;
			}
		}
		if(stp){
			cout<<"no"<<endl;
			continue;
		}
		int st = 0;
		int g,y;

		for(int j = 0; j < k ; j++){
			g = w[j].first;
			y = w[j].second;
			while(st<n){
				if(v[st] == g && y != 0){
					y--;
					mp[g]--;
					mp0[g]--;
				}
				else if(v[st] == g && y == 0){
					break;
				}
				else if(v[st] != g && mp[v[st]]>mp0[v[st]]){
					mp[v[st]]--;
				}
				else if(v[st] != g && mp[v[st]] == mp0[v[st]] && y == 0){
					break;
				}
				else{
					stp = true;
					break;
				}
				st++;
			}
			if(stp || (st == n && j != k-1) || (j == k-1 && st != n)){
				stp = true;
				break;
			}
		}
		cout<<(stp?"no":"yes")<<endl;
	}
}
Copy
Sorted Array Partitioning Duukh
GNU G++17
607 ms
11.4 MB
Accepted