Source Code
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define all(v) v.begin(), v.end()
#define pb push_back    
#define sz(x) (int)(x).size()
const int N = 1e5 + 5;
void solve() {
    
    int n, q;
    scanf("%d%d", &n, &q);
    vector<pii> aa(q), query;
    vi f(n + 1, 0), a(n);
    for(int i = 0; i < n; ++i)
        scanf("%d", &a[i]), ++f[a[i]];
    bool ok = 1, same = 1;
    for(int i = 0; i < q; ++i){
        scanf("%d%d", &aa[i].first, &aa[i].second);
        if(i == 0)
            query.pb({aa[i].first, aa[i].second});
        // if(i > 1 && aa[i - 1].first < aa[i - 2].first){
        //     ok = 0;
        // }
        // if(i && query.back().second > f[aa[i - 1].first]){
        //     ok = 0;
        // }
        // if(i)
        //     same &= (aa[i].first == aa[i - 1].first);
        if(i && aa[i].first == aa[i - 1].first)
            query.back().second += aa[i].second;
        else if(i)
            query.pb({aa[i].first, aa[i].second});
    }
    // for(auto [x, y] : query)
    //     printf("%d %d\n", x, y); 
    // if(ok == 0){
    //     puts("no");
    //     zer();
    //     return;
    // }`
    int m = sz(query);
    int idx = 0, c = 0;
    for(int i = 0; i < n; ++i){
        if(idx >= m){
            ok = 0;
            break;
        }
        auto [nm, goal] = query[idx]; 
        if(goal == c && a[i] == nm){
            ++idx;
            c = 0;
        }else if(goal == c && a[i] != nm){
            if(idx + 1 < m && query[idx + 1].first == a[i]){
                if(f[query[idx + 1].first] > query[idx + 1].second){
                    --f[query[idx + 1].first];
                    continue;
                }else if(f[query[idx + 1].first] == query[idx + 1].second){
                    ++idx;
                    c = 1;
                }
            }else{
                continue;
            }
        }else if(nm == a[i]){
            ++c;
        }else if(a[i] > nm){
            ok = 0;
            break;
        }
    }
            // cout << "HELLO";
    // printf("c = %d idx = %d\n", c, idx);
    if(idx != m - 1 || c != query[idx].second){
        ok = false;
    }
    // ok &= (idx == m && c == query[idx].second);
    if(ok)
        puts("yes");
    else
        puts("no");
}
int main() {
    int t = 1;
    scanf("%d",&t);
    while(t--)
        solve();
}
Copy
Sorted Array Partitioning noomaK
GNU G++17
119 ms
4.0 MB
Accepted