#include <bits/stdc++.h>
using namespace std;
int par[100005], sz[100005], tree[100005];
int ssz, mtree[400005];
int find(int x) {
if (x == par[x])return x;
return par[x] = find(par[x]);
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y)return;
par[x] = y;
sz[y] += sz[x];
}
void update(int idx, int val) {
idx++;
while (idx < 100005) {
tree[idx] += val;
idx += idx & (-idx);
}
}
int query(int idx) {
int ret = 0;
idx++;
while (idx) {
ret += tree[idx];
idx -= idx & (-idx);
}
return ret;
}
void mupdate(int idx, int val) {
idx += ssz;
while (idx) {
mtree[idx] = max(mtree[idx], val);
idx /= 2;
}
}
int mquery(int le, int ri) {
le += ssz;
ri += ssz;
int ret = 0;
while (le <= ri) {
if (le & 1)ret = max(ret, mtree[le++]);
if (!(ri & 1))ret = max(ret, mtree[ri--]);
le /= 2;
ri /= 2;
}
return ret;
}
int s[100005], e[100005];
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
for (int i = 0; i < N; i++) {
par[i] = i;
sz[i] = 1;
if(i) update(i, 1);
}
for (int i = 0; i < C; i++) {
int pre = -1;
int le, ri, mid, st;
le = 0; ri = N - 1;
st = 0;
while (le <= ri) {
mid = (le + ri) / 2;
if (query(mid) >= S[i]) {
st = mid;
ri = mid - 1;
}
else
le = mid + 1;
}
s[i] = st;
for (int j = S[i]; j <= E[i]; j++) {
int ss = sz[find(st)];
e[i] = st + ss - 1;
if (pre != -1)merge(pre, st);
pre = st;
st += ss;
}
}
ssz = 1;
while (ssz < N)ssz *= 2;
for (int i = 0; i < N - 1; i++)
mupdate(i, K[i]);
mupdate(N - 1, 0x3f3f3f3f);
vector<pair<int, int> > vec;
for (int i = 0; i < C; i++) {
if (mquery(s[i] + 1, e[i]) < R ||mquery(s[i], e[i] - 1) < R)
vec.emplace_back(s[i], e[i]);
}
sort(vec.begin(), vec.end(), [](pair<int, int> a, pair<int, int> b) {
if (a.second == b.second) {
return a.first < b.first;
}
return a.second > b.second;
});
vector<int> lis;
int ans = 0;
int idx = 0;
for (int i = 0; i < vec.size(); i++) {
auto it = upper_bound(lis.begin(), lis.end(), vec[i].first);
if (it == lis.end()) {
lis.push_back(vec[i].first);
ans = lis.size();
idx = vec[i].first;
}
else {
*it = vec[i].first;
int len = it - lis.begin() + 1;
if (ans < len || (ans == len && idx > vec[i].first)) {
ans = len;
idx = vec[i].first;
}
}
}
return idx;
}
Compilation message
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:100:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vec.size(); i++) {
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
28 ms |
4144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
