Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <iostream>
- #include <algorithm>
- #include <cmath>
- #include <string>
- #include <cstdlib>
- #include <vector>
- #include <queue>
- #include <set>
- #include <map>
- #include <cstdio>
- #include <iomanip>
- #define SWS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
- #define pb push_back
- #define ppb pop_back
- #define ft first
- #define sd second
- #define read freopen("minsumdiff.in", "r", stdin)
- #define write freopen("minsumdiff.out", "w", stdout)
- #define files read; write
- using namespace std;
- typedef long long ll;
- typedef pair<int, int> pii;
- typedef long double ld;
- const int Z = 3005;
- const int N = (int)2e5 + 228;
- const int INF = (int)1e9 + 228;
- const int MOD = (int)1e9 + 7;
- const ll LLINF = (ll)1e12 + 228;
- const ld eps = (ld)1.0 / 10000000;
- pii b[N];
- int a[N], mx[N];
- int main()
- {
- SWS;
- //files;
- int q;
- cin >> q;
- while (q--)
- {
- int n;
- cin >> n;
- for (int i = 1; i <= n; i++)
- cin >> a[i];
- int m;
- cin >> m;
- for (int i = 1; i <= m; i++)
- cin >> b[i].ft >> b[i].sd;
- sort(b + 1, b + 1 + m);
- for (int i = m; i > 0; i--)
- mx[i] = max(mx[i + 1], b[i].sd);
- int ans = 0, r = 0, cur = 0;
- bool f = true;
- for (int i = 1; i <= n; i++)
- {
- int ind = lower_bound(b + 1, b + 1 + m, (pii){a[i], -1}) - b;
- if (ind == m + 1)
- {
- f = false;
- break;
- }
- r = max(r, ind);
- cur++;
- if (mx[r] == cur)
- {
- cur = 0;
- ans++;
- r = 0;
- }
- else if (mx[r] < cur)
- {
- cur = 1;
- ans++;
- r = ind;
- }
- //cout << "DEBUG : " << i << ' ' << r << ' ' << ind << ' ' << cur << ' ' << ans << endl;
- }
- if (r != 0) ans++;
- if (f) cout << ans << "\n";
- else cout << -1 << "\n";
- for (int i = 1; i <= m; i++)
- {
- mx[i] = 0;
- b[i].ft = b[i].sd = 0;
- }
- for (int i = 1; i <= n; i++)
- a[i] = 0;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement