#define _FORTIFY_SOURCE 0
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include "teams.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef pair<int, int> pii;
const int maxn = 5e5 + 10;
const int maxq = 2e5 + 10;
pii v[maxn];
int n;
struct node {
node *l, *r;
int v;
node () {
l = r = nullptr;
v = 0;
}
};
inline int val(node *t) {
if (t != nullptr) return t->v;
return 0;
}
inline node* l(node* t) {
return t ? t->l : nullptr;
}
inline node* r(node *t ) {
return t ? t->r : nullptr;
}
inline int valor(node *t) {
return t ? t->v : 0;
}
void update(node *old, node *no, int p, int v, int ini=1, int fim=n) {
if (ini == fim) {
no->v = valor(old) + v;
return;
}
int meio = (ini + fim) >> 1;
if (p <= meio) {
if (old == nullptr || old->l == nullptr) no->l = new node;
else no->l = new node(*old->l);
if(old != nullptr && old->r != nullptr) no->r = old->r;
update(l(old), no->l, p, v, ini, meio);
}else {
if (old == nullptr || old->r == nullptr) no->r = new node;
else no->r = new node(*old->r);
if(old != nullptr && old->l != nullptr) no->l = old->l;
update(r(old), no->r, p, v, meio+1, fim);
}
no->v = val(no->l) + val(no->r);
}
int query(node *no, int l, int r, int ini=1, int fim=n) {
if(no == nullptr || ini > r || fim < l) return 0;
if(l <= ini && fim <= r) return no->v;
int meio = (ini + fim) >> 1;
int p1 = query(no->l, l, r, ini, meio);
int p2 = query(no->r, l, r, meio+1, fim);
return p1 + p2;
}
node* version[maxn];
int nv, ver[maxn];
void init(int N, int A[], int B[]) {
n = N;
for (int i = 1; i <= n; i++)
v[i] = {A[i-1], B[i-1]};
sort(v+1, v+n+1);
int last = 0;
for (int i = 1; i <= n; i++) {
if (v[i].ff != last) {
ver[last] = nv;
last = v[i].ff;
}
version[++nv] = new node;
update(version[nv-1], version[nv], v[i].ss, 1);
}
ver[last] = nv;
for (int i = 1; i <= n; i++)
ver[i] = max(ver[i-1], ver[i]);
//cout << "OI " << nv << '\n';
//for (int i = 1; i <= n; i++)
//cout << ver[i] << " \n"[i==nv];
}
int qtd[maxn];
typedef long long ll;
ll dp[maxn];
int freq[maxn];
inline ll solve(int l, int r, int ini, int fim) {
return query(version[ ver[r] ], ini, fim) - (l>0?query(version[ ver[l] ], ini, fim):0);
}
int can(int M, int K[]) {
vector<int> q;
ll sum = 0;
for (int i = 0; i < M; i++)
q.push_back(K[i]), sum += K[i];
if (sum > n) return 0;
for (auto& e : q)
freq[e]++;
sort(q.begin(), q.end());
q.erase(unique(q.begin(), q.end()), q.end());
bool certo = true;
int m = (int)q.size(); // m < sqrt(M)
for (int i = 0; i < m; i++) {
ll f = 1ll*freq[q[i]]*q[i]; // numero de caras na esquerda
dp[i] = solve(0, q[i], q[i], n) - f;
for (int j = 0; j < i; j++)
dp[i] = min(dp[i], dp[j] + solve(q[j], q[i], q[i], n) - f);
if (dp[i] < 0) { // vizinhanca menor que 0
certo = false;
break;
}
}
for (int i = 0; i < m; i++)
dp[i] = 0;
for (auto& e : q)
freq[e] = 0;
return certo;
}
// matching perfeito ( teorema de hall )
// S(vizinhanca de A) >= S(A) para todo o subset
Compilation message
teams.cpp:1: warning: "_FORTIFY_SOURCE" redefined
1 | #define _FORTIFY_SOURCE 0
|
<built-in>: note: this is the location of the previous definition
teams.cpp: In function 'void update(node*, node*, int, int, int, int)':
teams.cpp:44:68: warning: declaration of 'v' shadows a global declaration [-Wshadow]
44 | void update(node *old, node *no, int p, int v, int ini=1, int fim=n) {
| ^
teams.cpp:15:5: note: shadowed declaration is here
15 | pii v[maxn];
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
2 ms |
492 KB |
Output is correct |
7 |
Correct |
2 ms |
512 KB |
Output is correct |
8 |
Correct |
2 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
2 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
2 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
2 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
1 ms |
364 KB |
Output is correct |
26 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
145 ms |
59116 KB |
Output is correct |
2 |
Correct |
156 ms |
59628 KB |
Output is correct |
3 |
Correct |
146 ms |
59628 KB |
Output is correct |
4 |
Correct |
164 ms |
60912 KB |
Output is correct |
5 |
Correct |
125 ms |
59392 KB |
Output is correct |
6 |
Correct |
112 ms |
59268 KB |
Output is correct |
7 |
Correct |
116 ms |
59372 KB |
Output is correct |
8 |
Correct |
107 ms |
59244 KB |
Output is correct |
9 |
Correct |
97 ms |
57856 KB |
Output is correct |
10 |
Correct |
98 ms |
57068 KB |
Output is correct |
11 |
Correct |
116 ms |
60140 KB |
Output is correct |
12 |
Correct |
107 ms |
57068 KB |
Output is correct |
13 |
Correct |
113 ms |
60268 KB |
Output is correct |
14 |
Correct |
111 ms |
58092 KB |
Output is correct |
15 |
Correct |
140 ms |
59620 KB |
Output is correct |
16 |
Correct |
135 ms |
59628 KB |
Output is correct |
17 |
Correct |
120 ms |
60524 KB |
Output is correct |
18 |
Correct |
129 ms |
60524 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
164 ms |
59756 KB |
Output is correct |
2 |
Correct |
151 ms |
60396 KB |
Output is correct |
3 |
Correct |
264 ms |
64204 KB |
Output is correct |
4 |
Correct |
149 ms |
60912 KB |
Output is correct |
5 |
Correct |
3995 ms |
60196 KB |
Output is correct |
6 |
Correct |
2800 ms |
60296 KB |
Output is correct |
7 |
Correct |
115 ms |
60012 KB |
Output is correct |
8 |
Correct |
2147 ms |
60040 KB |
Output is correct |
9 |
Correct |
95 ms |
57708 KB |
Output is correct |
10 |
Correct |
105 ms |
57548 KB |
Output is correct |
11 |
Correct |
161 ms |
60752 KB |
Output is correct |
12 |
Correct |
1686 ms |
58164 KB |
Output is correct |
13 |
Correct |
468 ms |
61292 KB |
Output is correct |
14 |
Correct |
303 ms |
62316 KB |
Output is correct |
15 |
Correct |
210 ms |
60584 KB |
Output is correct |
16 |
Correct |
210 ms |
60524 KB |
Output is correct |
17 |
Correct |
236 ms |
61328 KB |
Output is correct |
18 |
Correct |
205 ms |
61332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
912 ms |
327404 KB |
Output is correct |
2 |
Correct |
925 ms |
331860 KB |
Output is correct |
3 |
Correct |
1320 ms |
339756 KB |
Output is correct |
4 |
Correct |
916 ms |
334312 KB |
Output is correct |
5 |
Execution timed out |
4116 ms |
330688 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |