Codeforces 1257D - Yet Another Monster Killing Problem

#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define LL long long
using namespace std;
const int maxn = (ll) 2e5 + 5;
const int mod = 1000000007;
const int inf = 0x3f3f3f3f;

struct node {
    int p, s;

    bool operator<(const node &b) {//用做排序
        return p < b.p;
    }
} b[maxn];

bool cmp(const node &x, int y) {//用做二分
    return x.p < y;
}

int a[maxn];

int main() {
    start;
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        int maxa = 0, maxs = 0;//用做判-1
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            maxa = max(maxa, a[i]);
        }
        int m;
        cin >> m;
        for (int i = 1; i <= m; ++i) {
            cin >> b[i].p >> b[i].s;
            maxs = max(maxs, b[i].p);
        }
        if (maxa > maxs) {
            cout << -1 << '\n';
            continue;
        }
        sort(b + 1, b + m + 1);
        for (int i = m - 1; i >= 1; --i)//后缀操作
            b[i].s = max(b[i].s, b[i + 1].s);
        int k = 1;
        int last = 0;
        int minn = inf;
        for (int i = 1; i <= n; ++i) {
            int t = lower_bound(b + 1, b + m + 1, a[i], cmp) - b;//刚好能杀死该怪物的英雄编号
            minn = min(b[t].s, minn);//今天所需要的最小耐力
            if (minn + last < i) {//将这只怪物放到明天杀
                minn = b[t].s;
                ++k;
                last = i - 1;
            }
        }
        cout << k << '\n';
    }
    return 0;
}