#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "teams.h"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int INF = 1e9 + 7;
const int MAXN = 1e6 + 5;
int dp[MAXN];
int L[MAXN*50], R[MAXN*50], tree[MAXN*50];
int cnt = 0, m = 0, n = 0, root[MAXN*50];
vi pos, d, arr[MAXN];
int create(int k) {
int ret = cnt++;
tree[ret] = tree[k];
L[ret] = L[k], R[ret] = R[k];
return ret;
}
int qry(int l, int r, int k, int x, int y) {
if (y < l || r < x) return 0;
if (x <= l && r <= y)
return tree[k];
int mi = (l + r) / 2;
return qry(l, mi, L[k], x, y) + qry(mi + 1, r, R[k], x, y);
}
int upd(int l, int r, int k, int x, int v) {
if (r < x || x < l) return k;
int nk = create(k);
if (x <= l && r <= x) {
tree[nk] += v;
return nk;
}
int mi = (l + r) / 2;
L[nk] = upd(l, mi, L[nk], x, v);
R[nk] = upd(mi + 1, r, R[nk], x, v);
tree[nk] = tree[L[nk]] + tree[R[nk]];
return nk;
}
int build(int l, int r) {
int cur = cnt++;
if (l == r)
return cur;
int mi = (l + r) / 2;
L[cur] = build(l, mi);
R[cur] = build(mi + 1, r);
tree[cur] = tree[L[cur]] + tree[R[cur]];
return cur;
}
void init(int n, int a[], int b[]) {
::n = n;
for (int i = 0; i < n; i++)
arr[a[i] - 1].pb(b[i]);
root[n] = build(0, n+1);
for (int i = n - 1; i >= 0; i--) {
root[i] = root[i + 1];
for (int j: arr[i])
root[i] = upd(0, n+1, root[i], j, 1);
}
}
int gt(int x, int y) {
int lo = y, hi = m + 1;
while (lo < hi) {
int mi = (lo + hi) / 2;
if (dp[x] + qry(0, n+1, root[pos[x]], 0, pos[mi] - 1) >= dp[y] + qry(0, n+1, root[pos[y]], 0, pos[mi] - 1))
hi = mi;
else
lo = mi + 1;
}
for (int i = y; i <= m + 1; i++)
if (dp[x] + qry(0, n+1, root[pos[x]], 0, pos[i] - 1) >= dp[y] + qry(0, n+1, root[pos[y]], 0, pos[i] - 1))
return i;
exit(-1);
return lo;
}
int can(int m, int k[]) {
::m = m;
pos = {0};
vi tmp;
for (int i = 0; i < m; i++) {
pos.pb(k[i]);
tmp.pb(k[i]);
}
sort(pos.begin(), pos.end());
d.clear();
int curCnt = 0;
for (int i = 0; i <= m; i++) {
if (i > 0) {
while (d.size() > 1 && gt(d[d.size()-2], d.back()) <= i)
d.pop_back();
dp[i] = dp[d.back()] + qry(0, n+1, root[pos[d.back()]], 0, pos[i] - 1) + pos[i];
}
curCnt = max(curCnt, dp[i] + qry(0, n+1, root[pos[i]], 0, n));
if (curCnt > n)
return 0;
while (d.size() > 1 && gt(d[d.size()-2], d.back()) <= gt(d.back(), i))
d.pop_back();
d.pb(i);
}
return 1;
}
Compilation message
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:61:34: warning: declaration of 'n' shadows a global declaration [-Wshadow]
void init(int n, int a[], int b[]) {
^
teams.cpp:18:21: note: shadowed declaration is here
int cnt = 0, m = 0, n = 0, root[MAXN*50];
^
teams.cpp: In function 'int gt(int, int)':
teams.cpp:82:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int i = y; i <= m + 1; i++)
^~~
teams.cpp:85:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
exit(-1);
^~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:89:23: warning: declaration of 'm' shadows a global declaration [-Wshadow]
int can(int m, int k[]) {
^
teams.cpp:18:14: note: shadowed declaration is here
int cnt = 0, m = 0, n = 0, root[MAXN*50];
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
27 ms |
23808 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
155 ms |
49912 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
161 ms |
50008 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1012 ms |
167524 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
