#include "teams.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define prev Prev
#define f first
#define s second
using namespace std;
const int N = 15e5 + 5;
int le_[N * 20], ri_[N * 20], root[N], tree[N * 20], n, cur, prev[N], k[N], a[N], b[N], nxt[N], p[N], rem[N];
long long dp[N];
void build(int u,int l,int r) {
if(l == r) return;
int mid = (l + r) / 2;
le_[u] = ++cur; ri_[u] = ++cur;
build(le_[u], l, mid); build(ri_[u], mid + 1, r);
}
void upd(int u,int st,int en,int l,int r) {
if(l > en || r < st) return;
le_[cur] = le_[u], ri_[cur] = ri_[u];
tree[cur] = tree[u];
assert(cur <= N * 35);
if(st <= l && r <= en) {
tree[cur]++;
return;
}
int mid = (l + r) / 2, x = cur;
if(st <= mid) {
le_[x] = ++cur;
}
upd(le_[u], st, en, l, mid);
if(en > mid) {
ri_[x] = ++cur;
}
upd(ri_[u], st, en, mid + 1, r);
}
int get(int u,int id, int l,int r) {
if(id > r || id < l) return 0;
if(l == r) return tree[u];
int mid = (l + r) >> 1;
if(id <= mid) return tree[u] + get(le_[u], id, l, mid);
return tree[u] + get(ri_[u], id, mid + 1, r);
}
void init(int N, int A[], int B[]) {
n = N;
vector<int> V[n + 2];
for(int i = 0; i < n; i++) V[A[i]].push_back(B[i]);
cur = root[n + 1] = 1;
build(1, 1, n);
for(int i = n; i >= 1; i--) {
root[i] = root[i + 1];
for(int j = 0; j < V[i].size(); j++) {
cur++;
int x = cur;
upd(root[i], i, V[i][j], 1, n);
root[i] = x;
}
}
}
int get(int i, int j) {
int l = k[j] + 1, r = n, ans = n + 1;
while(l <= r) {
int mid = (l + r) / 2;
if(dp[i] - get(root[k[i] + 1], mid, 1, n) >= dp[j] - get(root[k[j] + 1], mid, 1, n)) ans = mid, r = mid - 1;
else l = mid + 1;
}
return ans;
}
int can(int M, int K[]) {
sort(K, K + M);
vector<int> s; set<pii> bet;
s.push_back(0);
for(int i = 1; i <= M; i++) {
k[i] = K[i - 1]; rem[i] = 0; nxt[i] = p[i] = 0;
}
for(int i = 1; i <= M; i++) {
while(bet.size() && (*bet.begin()).f <= k[i]) {
pii po = *bet.begin();
bet.erase(po);
int r = po.s, l = p[r];
rem[r] = 1;
if(nxt[r]) {
nxt[l] = nxt[r];
p[nxt[l]] = l;
int x = nxt[l];
bet.erase({prev[x], x});
prev[x] = get(l, x);
bet.insert({prev[x], x});
}
}
while(s.size() && rem[s.back()]) s.pop_back();
int x = s.back();
dp[i] = dp[x] + k[i] - get(root[k[x] + 1], k[i], 1, n);
prev[i] = get(x, i);s.push_back(i); nxt[x] = i; p[i] = x;
bet.insert({prev[i], i});
if(dp[i] > 0) return 0;
}
return 1;
}
/*
int main() {
// _inputFile = fopen("teams.in", "rb");
// _outputFile = fopen("teams.out", "w");
int n, q;
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i] >> b[i];
init(n, a, b);
cin >> q;
while(q--) {
int k;
cin >> k;
int v[k + 2];
for(int i = 0; i < k; i++) cin >> v[i];
cout << can(k, v) << endl;
}
return 0;
} */
Compilation message
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:43:15: warning: declaration of 'N' shadows a global declaration [-Wshadow]
43 | void init(int N, int A[], int B[]) {
| ~~~~^
teams.cpp:8:11: note: shadowed declaration is here
8 | const int N = 15e5 + 5;
| ^
teams.cpp:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(int j = 0; j < V[i].size(); j++) {
| ~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
588 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
0 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
0 ms |
332 KB |
Output is correct |
23 |
Correct |
0 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
104 ms |
58980 KB |
Output is correct |
2 |
Correct |
114 ms |
58996 KB |
Output is correct |
3 |
Correct |
95 ms |
58960 KB |
Output is correct |
4 |
Correct |
95 ms |
60892 KB |
Output is correct |
5 |
Correct |
28 ms |
26864 KB |
Output is correct |
6 |
Correct |
31 ms |
26888 KB |
Output is correct |
7 |
Correct |
35 ms |
26828 KB |
Output is correct |
8 |
Correct |
30 ms |
26864 KB |
Output is correct |
9 |
Correct |
50 ms |
9460 KB |
Output is correct |
10 |
Correct |
47 ms |
26948 KB |
Output is correct |
11 |
Correct |
29 ms |
27080 KB |
Output is correct |
12 |
Correct |
30 ms |
30396 KB |
Output is correct |
13 |
Correct |
53 ms |
46188 KB |
Output is correct |
14 |
Correct |
41 ms |
26736 KB |
Output is correct |
15 |
Correct |
91 ms |
57052 KB |
Output is correct |
16 |
Correct |
86 ms |
56628 KB |
Output is correct |
17 |
Correct |
41 ms |
34884 KB |
Output is correct |
18 |
Correct |
64 ms |
46412 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
122 ms |
58920 KB |
Output is correct |
2 |
Correct |
105 ms |
58976 KB |
Output is correct |
3 |
Correct |
834 ms |
60520 KB |
Output is correct |
4 |
Correct |
97 ms |
60568 KB |
Output is correct |
5 |
Correct |
180 ms |
26836 KB |
Output is correct |
6 |
Correct |
161 ms |
26820 KB |
Output is correct |
7 |
Correct |
36 ms |
26820 KB |
Output is correct |
8 |
Correct |
127 ms |
26836 KB |
Output is correct |
9 |
Correct |
50 ms |
9436 KB |
Output is correct |
10 |
Correct |
145 ms |
27200 KB |
Output is correct |
11 |
Correct |
140 ms |
27204 KB |
Output is correct |
12 |
Correct |
168 ms |
30456 KB |
Output is correct |
13 |
Correct |
444 ms |
46232 KB |
Output is correct |
14 |
Correct |
1002 ms |
55132 KB |
Output is correct |
15 |
Correct |
306 ms |
56868 KB |
Output is correct |
16 |
Correct |
307 ms |
56908 KB |
Output is correct |
17 |
Correct |
226 ms |
38852 KB |
Output is correct |
18 |
Correct |
272 ms |
56564 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
694 ms |
333304 KB |
Output is correct |
2 |
Correct |
703 ms |
333416 KB |
Output is correct |
3 |
Correct |
3333 ms |
333696 KB |
Output is correct |
4 |
Correct |
729 ms |
343352 KB |
Output is correct |
5 |
Correct |
577 ms |
150000 KB |
Output is correct |
6 |
Correct |
534 ms |
150016 KB |
Output is correct |
7 |
Correct |
156 ms |
149980 KB |
Output is correct |
8 |
Correct |
443 ms |
150128 KB |
Output is correct |
9 |
Correct |
308 ms |
50064 KB |
Output is correct |
10 |
Correct |
444 ms |
166260 KB |
Output is correct |
11 |
Correct |
437 ms |
166520 KB |
Output is correct |
12 |
Correct |
568 ms |
191156 KB |
Output is correct |
13 |
Correct |
1867 ms |
270968 KB |
Output is correct |
14 |
Correct |
3554 ms |
315276 KB |
Output is correct |
15 |
Correct |
1108 ms |
326836 KB |
Output is correct |
16 |
Correct |
1108 ms |
324916 KB |
Output is correct |
17 |
Correct |
784 ms |
254988 KB |
Output is correct |
18 |
Correct |
786 ms |
264068 KB |
Output is correct |