#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 5e5 + 10;
const int lg = 22;
const int inf = 1e9;
int n, a[maxn], b[maxn], seg[maxn*lg], lc[maxn*lg], rc[maxn*lg], root[maxn], vercnt = 1;
vector<int> val[maxn];
void build(int v, int l, int r){
if (l + 1 == r){
return;
}
lc[v] = vercnt++;
rc[v] = vercnt++;
int mid = (l + r) >> 1;
build(lc[v], l, mid);
build(rc[v], mid, r);
}
void add(int v, int newv, int l, int r, int idx){
if (l + 1 == r){
seg[newv] = seg[v] + 1;
return;
}
int mid = (l + r) >> 1;
if (idx < mid){
lc[newv] = vercnt++;
rc[newv] = rc[v];
add(lc[v], lc[newv], l, mid, idx);
}
else{
lc[newv] = lc[v];
rc[newv] = vercnt++;
add(rc[v], rc[newv], mid, r, idx);
}
seg[newv] = seg[lc[newv]] + seg[rc[newv]];
}
int get(int v, int l, int r, int ql, int qr){
if (qr <= l || r <= ql) return 0;
if (ql <= l && r <= qr) return seg[v];
int mid = (l + r) >> 1;
return get(lc[v], l, mid, ql, qr)
+ get(rc[v], mid, r, ql, qr);
}
void init(int N, int A[], int B[]){
n = N;
for (int i = 0; i < n; i++){
val[A[i]].push_back(B[i]);
}
root[0] = 0;
build(0, 1, n+1);
for (int i = 1; i <= n; i++){
root[i] = root[i-1];
for (auto x: val[i]){
int tmp = vercnt++;
add(root[i], tmp, 1, n+1, x);
root[i] = tmp;
}
}
}
int k[maxn], dp[maxn], func[maxn << 2];
int f(int idx, int x){
// debug(idx, x, dp[idx], get(root[x], 1, n+1, x, n+1), get(root[k[idx]], 1, n+1, x, n+1));
if (k[idx] > x) return -inf - idx;
return dp[idx] + get(root[x], 1, n+1, x, n+1) - get(root[k[idx]], 1, n+1, x, n+1);
}
vector<int> del;
bool mark[maxn << 2];
void addfunc(int v, int l, int r, int idx){
// debug(v, l, r, idx);
if (!mark[v]){
mark[v] = true;
del.push_back(v);
}
int mid = (l + r) >> 1;
bool L = f(idx, l) < f(func[v], l);
bool M = f(idx, mid) < f(func[v], mid);
if (M){
swap(func[v], idx);
}
// debug(func[v]);
if (l + 1 == r) return;
if (L != M){
addfunc(v << 1, l, mid, idx);
}
else{
addfunc(v << 1 | 1, mid, r, idx);
}
}
int getmin(int v, int l, int r, int idx){
if (l + 1 == r) return f(func[v], idx);
int mid = (l + r) >> 1;
if (idx < mid) return min(f(func[v], idx), getmin(v << 1, l, mid, idx));
else return min(f(func[v], idx), getmin(v << 1 | 1, mid, r, idx));
}
int can(int M, int K[]) {
for (auto x: del){
func[x] = 0;
mark[x] = false;
}
del.clear();
sort(K, K+M);
for (int i = 1; i <= M; i++){
k[i] = K[i-1];
}
dp[0] = 0;
for (int i = 1; i <= M; i++){
dp[i] = getmin(1, 1, n+1, k[i]) - k[i];
// debug(i, dp[i]);
if (dp[i] < 0) return 0;
addfunc(1, 1, n+1, i);
}
return 1;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
11988 KB |
Output is correct |
2 |
Correct |
6 ms |
11980 KB |
Output is correct |
3 |
Correct |
6 ms |
12088 KB |
Output is correct |
4 |
Correct |
6 ms |
12028 KB |
Output is correct |
5 |
Correct |
5 ms |
12116 KB |
Output is correct |
6 |
Correct |
6 ms |
12144 KB |
Output is correct |
7 |
Correct |
8 ms |
12128 KB |
Output is correct |
8 |
Correct |
10 ms |
12116 KB |
Output is correct |
9 |
Correct |
6 ms |
12116 KB |
Output is correct |
10 |
Correct |
7 ms |
12116 KB |
Output is correct |
11 |
Correct |
7 ms |
12116 KB |
Output is correct |
12 |
Correct |
11 ms |
12116 KB |
Output is correct |
13 |
Correct |
11 ms |
12128 KB |
Output is correct |
14 |
Correct |
7 ms |
12116 KB |
Output is correct |
15 |
Correct |
6 ms |
12116 KB |
Output is correct |
16 |
Correct |
6 ms |
12116 KB |
Output is correct |
17 |
Correct |
6 ms |
12116 KB |
Output is correct |
18 |
Correct |
6 ms |
11988 KB |
Output is correct |
19 |
Correct |
6 ms |
11988 KB |
Output is correct |
20 |
Correct |
6 ms |
12116 KB |
Output is correct |
21 |
Correct |
7 ms |
12160 KB |
Output is correct |
22 |
Correct |
7 ms |
12116 KB |
Output is correct |
23 |
Correct |
6 ms |
12116 KB |
Output is correct |
24 |
Correct |
6 ms |
12116 KB |
Output is correct |
25 |
Correct |
6 ms |
11988 KB |
Output is correct |
26 |
Correct |
6 ms |
12116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
50 ms |
37416 KB |
Output is correct |
2 |
Correct |
57 ms |
37444 KB |
Output is correct |
3 |
Correct |
50 ms |
37324 KB |
Output is correct |
4 |
Correct |
51 ms |
38160 KB |
Output is correct |
5 |
Correct |
30 ms |
36392 KB |
Output is correct |
6 |
Correct |
28 ms |
36268 KB |
Output is correct |
7 |
Correct |
27 ms |
36284 KB |
Output is correct |
8 |
Correct |
27 ms |
36308 KB |
Output is correct |
9 |
Correct |
302 ms |
36780 KB |
Output is correct |
10 |
Correct |
143 ms |
35464 KB |
Output is correct |
11 |
Correct |
46 ms |
36512 KB |
Output is correct |
12 |
Correct |
28 ms |
36544 KB |
Output is correct |
13 |
Correct |
36 ms |
35708 KB |
Output is correct |
14 |
Correct |
37 ms |
36804 KB |
Output is correct |
15 |
Correct |
51 ms |
37376 KB |
Output is correct |
16 |
Correct |
46 ms |
37224 KB |
Output is correct |
17 |
Correct |
30 ms |
36560 KB |
Output is correct |
18 |
Correct |
32 ms |
36692 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
62 ms |
37884 KB |
Output is correct |
2 |
Correct |
60 ms |
37992 KB |
Output is correct |
3 |
Correct |
665 ms |
40812 KB |
Output is correct |
4 |
Correct |
56 ms |
38220 KB |
Output is correct |
5 |
Correct |
707 ms |
36768 KB |
Output is correct |
6 |
Correct |
623 ms |
36676 KB |
Output is correct |
7 |
Correct |
36 ms |
36684 KB |
Output is correct |
8 |
Correct |
452 ms |
36724 KB |
Output is correct |
9 |
Correct |
334 ms |
36804 KB |
Output is correct |
10 |
Correct |
665 ms |
35672 KB |
Output is correct |
11 |
Correct |
813 ms |
36820 KB |
Output is correct |
12 |
Correct |
861 ms |
36880 KB |
Output is correct |
13 |
Correct |
950 ms |
36272 KB |
Output is correct |
14 |
Correct |
821 ms |
39696 KB |
Output is correct |
15 |
Correct |
689 ms |
37964 KB |
Output is correct |
16 |
Correct |
687 ms |
37932 KB |
Output is correct |
17 |
Correct |
644 ms |
37212 KB |
Output is correct |
18 |
Correct |
659 ms |
37036 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
492 ms |
152864 KB |
Output is correct |
2 |
Correct |
455 ms |
152900 KB |
Output is correct |
3 |
Correct |
2160 ms |
158748 KB |
Output is correct |
4 |
Correct |
450 ms |
160588 KB |
Output is correct |
5 |
Correct |
1801 ms |
151504 KB |
Output is correct |
6 |
Correct |
1581 ms |
151500 KB |
Output is correct |
7 |
Correct |
124 ms |
151432 KB |
Output is correct |
8 |
Correct |
1307 ms |
151476 KB |
Output is correct |
9 |
Correct |
1914 ms |
152040 KB |
Output is correct |
10 |
Correct |
1924 ms |
149148 KB |
Output is correct |
11 |
Correct |
2067 ms |
149848 KB |
Output is correct |
12 |
Correct |
2256 ms |
150708 KB |
Output is correct |
13 |
Correct |
2787 ms |
154428 KB |
Output is correct |
14 |
Correct |
2529 ms |
163336 KB |
Output is correct |
15 |
Correct |
1901 ms |
158928 KB |
Output is correct |
16 |
Correct |
1931 ms |
158892 KB |
Output is correct |
17 |
Correct |
1682 ms |
153428 KB |
Output is correct |
18 |
Correct |
1715 ms |
153368 KB |
Output is correct |