#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
const int N = 5e5 + 10;
pair<int, int> a[N];
int n;
int last[N], pref[N], timer[N];
struct node {
int left, right, sum;
};
node T[N * 20 + 10];
int cnt, it[N], idx[N];
vector<pair<int, int> > rrh;
void up(int s, int l, int r, int pos, int val) {
if (l == r) {
T[s].sum += val;
return;
}
int mid = l + r >> 1;
if (pos <= mid) {
T[++cnt] = T[T[s].left];
T[s].left = cnt;
up(T[s].left, l, mid, pos, val);
}
else {
T[++cnt] = T[T[s].right];
T[s].right = cnt;
up(T[s].right, mid + 1, r, pos, val);
}
T[s].sum = T[T[s].left].sum + T[T[s].right].sum;
}
int get(int s, int l, int r, int from, int to) {
if (l > to || r < from || !s) return 0;
if (from <= l && r <= to) return T[s].sum;
int mid = l + r >> 1;
return get(T[s].left, l, mid, from, to) + get(T[s].right, mid + 1, r, from, to);
}
int tree_idx (int x) {
return upper_bound(all(rrh), make_pair(x, 0)) - rrh.begin() + 1;
}
void init(int _n, int A[], int B[]) {
n = _n;
for(int i = 1; i <= n; i++) {
a[i] = make_pair(A[i - 1], B[i - 1]);
}
sort(a + 1, a + n + 1);
for(int i = 1; i <= n; i++) {
rrh.emplace_back(a[i].second, i);
}
sort(all(rrh));
rrh.resize(unique(all(rrh)) - rrh.begin());
for(int i = 1; i <= n; i++) {
int old = a[i].second;
a[i].second = upper_bound(all(rrh), make_pair(a[i].second, i)) - rrh.begin();
idx[old] = max(idx[old], a[i].second);
}
for(int i = 1; i <= n; i++) {
if (idx[i] == 0) idx[i] = idx[i - 1];
}
for(int i = 1, j = 1; i <= n; i++) {
T[it[i] = ++cnt] = T[it[i - 1]];
while (j <= n && a[j].first == i) {
up(it[i], 1, n, a[j].second, 1);
j++;
}
}
// for(int i = 1; i <= n; i++) cout << a[i].first << " " << a[i].second << endl;
}
int can (int m, int k[]) {
sort(k, k + m);
for(int i = 0, p = 0; i < m; i++) {
int sz = k[i];
auto calc = [&] (int x) {
int total = get(it[sz], 1, n, 1, x);
int lost = 0;
if (!p) return total;
int l = 1, r = p, pos = 0;
while (l <= r) {
int mid = l + r >> 1;
if (last[mid] >= x) {
pos = mid;
l = mid + 1;
} else r = mid - 1;
}
lost = pref[p] - pref[pos];
if (pos) {
last[p + 1] = 0;
lost += get(it[timer[pos]], 1, n, last[pos + 1] + 1, x);
}
return total - lost;
};
// if (i == 1) cout << calc(1) << endl;
// if (i == 0) {
// cout << calc(1) << endl;
// return 0;
// }
int not_use = calc(idx[sz - 1]);
// if (i == 0) cout << calc(1) << endl;
// if (i == 0) {
// cout << sz - 1 << endl;
// cout << idx[sz - 1] << endl;
// cout << not_use << endl;
// }
int l = 1, r = n, smallest = 0;
while (l <= r) {
int mid = l + r >> 1;
if (calc(mid) - not_use >= sz) {
smallest = mid;
r = mid - 1;
} else l = mid + 1;
}
// cout << smallest << endl;
// cout << calc(smallest) << " " << not_use << endl;
if (!smallest) return 0;
while (p && last[p] <= smallest) p--;
if (p) {
pref[p] = get(it[timer[p]], 1, n, smallest + 1, last[p]);
if (p) pref[p] += pref[p - 1];
}
++p;
pref[p] = pref[p - 1] + get(it[sz], 1, n, 1, smallest);
last[p] = smallest;
timer[p] = sz;
}
return 1;
}
#ifdef ngu
int32_t main() {
freopen ("task.inp", "r", stdin);
freopen ("task.out", "w", stdout);
int n; cin >> n;
int *A = (int *)malloc(sizeof(int) * (unsigned int)N);
int *B = (int *)malloc(sizeof(int) * (unsigned int)N);
for(int i = 0; i < n; i++) cin >> A[i] >> B[i];
init(n, A, B);
int q; cin >> q;
while (q--) {
int m; cin >> m;
int *k = (int *)malloc(sizeof(int) * (unsigned int)m);
for(int i = 0; i < m; i++) cin >> k[i];
cout << can(m, k) << endl;
}
}
#endif // ngu
Compilation message
teams.cpp: In function 'void up(int, int, int, int, int)':
teams.cpp:32:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
32 | int mid = l + r >> 1;
| ~~^~~
teams.cpp: In function 'int get(int, int, int, int, int)':
teams.cpp:49:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
49 | int mid = l + r >> 1;
| ~~^~~
teams.cpp: In function 'int tree_idx(int)':
teams.cpp:54:63: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
54 | return upper_bound(all(rrh), make_pair(x, 0)) - rrh.begin() + 1;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:75:68: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
75 | a[i].second = upper_bound(all(rrh), make_pair(a[i].second, i)) - rrh.begin();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
teams.cpp: In lambda function:
teams.cpp:105:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
105 | int mid = l + r >> 1;
| ~~^~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:134:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
134 | int mid = l + r >> 1;
| ~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4440 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
2 ms |
4444 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
1 ms |
4444 KB |
Output is correct |
16 |
Correct |
1 ms |
4444 KB |
Output is correct |
17 |
Correct |
1 ms |
4444 KB |
Output is correct |
18 |
Correct |
1 ms |
4444 KB |
Output is correct |
19 |
Correct |
1 ms |
4444 KB |
Output is correct |
20 |
Correct |
1 ms |
4444 KB |
Output is correct |
21 |
Correct |
1 ms |
4444 KB |
Output is correct |
22 |
Correct |
1 ms |
4440 KB |
Output is correct |
23 |
Correct |
1 ms |
4444 KB |
Output is correct |
24 |
Correct |
1 ms |
4440 KB |
Output is correct |
25 |
Correct |
1 ms |
4444 KB |
Output is correct |
26 |
Correct |
1 ms |
4444 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
59 ms |
30920 KB |
Output is correct |
2 |
Correct |
57 ms |
31012 KB |
Output is correct |
3 |
Correct |
54 ms |
29028 KB |
Output is correct |
4 |
Correct |
56 ms |
31532 KB |
Output is correct |
5 |
Correct |
35 ms |
30664 KB |
Output is correct |
6 |
Correct |
34 ms |
30660 KB |
Output is correct |
7 |
Correct |
33 ms |
30660 KB |
Output is correct |
8 |
Correct |
33 ms |
30740 KB |
Output is correct |
9 |
Correct |
107 ms |
30832 KB |
Output is correct |
10 |
Correct |
61 ms |
30332 KB |
Output is correct |
11 |
Correct |
33 ms |
30400 KB |
Output is correct |
12 |
Correct |
30 ms |
30672 KB |
Output is correct |
13 |
Correct |
39 ms |
30724 KB |
Output is correct |
14 |
Correct |
39 ms |
28872 KB |
Output is correct |
15 |
Correct |
48 ms |
30936 KB |
Output is correct |
16 |
Correct |
58 ms |
30932 KB |
Output is correct |
17 |
Correct |
35 ms |
30904 KB |
Output is correct |
18 |
Correct |
37 ms |
30920 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
58 ms |
31684 KB |
Output is correct |
2 |
Correct |
61 ms |
31688 KB |
Output is correct |
3 |
Correct |
281 ms |
35012 KB |
Output is correct |
4 |
Correct |
54 ms |
31432 KB |
Output is correct |
5 |
Correct |
210 ms |
31320 KB |
Output is correct |
6 |
Correct |
188 ms |
31248 KB |
Output is correct |
7 |
Correct |
40 ms |
31320 KB |
Output is correct |
8 |
Correct |
149 ms |
31380 KB |
Output is correct |
9 |
Correct |
105 ms |
30828 KB |
Output is correct |
10 |
Correct |
204 ms |
30932 KB |
Output is correct |
11 |
Correct |
202 ms |
30916 KB |
Output is correct |
12 |
Correct |
265 ms |
31116 KB |
Output is correct |
13 |
Correct |
285 ms |
31696 KB |
Output is correct |
14 |
Correct |
313 ms |
33492 KB |
Output is correct |
15 |
Correct |
147 ms |
31688 KB |
Output is correct |
16 |
Correct |
152 ms |
31756 KB |
Output is correct |
17 |
Correct |
152 ms |
31560 KB |
Output is correct |
18 |
Correct |
146 ms |
31708 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
419 ms |
145356 KB |
Output is correct |
2 |
Correct |
400 ms |
145344 KB |
Output is correct |
3 |
Correct |
1228 ms |
152164 KB |
Output is correct |
4 |
Correct |
380 ms |
145124 KB |
Output is correct |
5 |
Correct |
637 ms |
142776 KB |
Output is correct |
6 |
Correct |
636 ms |
142780 KB |
Output is correct |
7 |
Correct |
183 ms |
142556 KB |
Output is correct |
8 |
Correct |
542 ms |
142756 KB |
Output is correct |
9 |
Correct |
640 ms |
142924 KB |
Output is correct |
10 |
Correct |
677 ms |
141064 KB |
Output is correct |
11 |
Correct |
849 ms |
141864 KB |
Output is correct |
12 |
Correct |
834 ms |
142524 KB |
Output is correct |
13 |
Correct |
1136 ms |
144320 KB |
Output is correct |
14 |
Correct |
1428 ms |
149152 KB |
Output is correct |
15 |
Correct |
563 ms |
145336 KB |
Output is correct |
16 |
Correct |
626 ms |
145496 KB |
Output is correct |
17 |
Correct |
519 ms |
144856 KB |
Output is correct |
18 |
Correct |
510 ms |
144700 KB |
Output is correct |