#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;
typedef pair<lint, lint> plint;
const int MAX = 2e5 + 10;
int n, c, r, K[MAX], S[MAX], E[MAX], Par[MAX], Dp[MAX], Dep[MAX];
vector<int> G[MAX];
void update(int a) {
K[a] = 0;
for (int x : G[a]) K[a] = max(K[a], K[x]);
}
int GetBestPosition(int N, int C, int R, int *k, int *s, int *e) {
n = N; c = C; r = R; K[0] = r;
for (int i = 1; i < n; i++) K[i] = k[i - 1];
for (int i = 0; i < c; i++) S[i] = s[i], E[i] = e[i];
vector<int> V; int p = 0;
for (int i = 0; i < c; i++) {
while (V.size() <= E[i]) V.push_back(p++);
while (V.size() > S[i]) Par[V.back()] = n, V.pop_back();
V.push_back(n++);
}
for (int i = 0; i < n - 1; i++) {
G[Par[i]].push_back(i); K[Par[i]] = max(K[Par[i]], K[i]);
}
for (int i = n - 2; i >= 0; i--) {
if (K[Par[i]] == K[i]) Dp[i] = Dp[Par[i]] + 1;
Dep[i] = Dep[Par[i]] + 1;
}
for (int j = 0; j < n; j++) cout << Dp[j] << ' ';
cout << '\n';
pint ans = { -1, -1 }; vector<int> W;
for (int i = 0; i < n - c - 1; i++) {
ans = max(ans, { Dp[i], -i }); swap(K[i], K[i + 1]);
int x = i, y = i + 1;
if (Dep[x] < Dep[y]) swap(x, y);
W.push_back(x); W.push_back(y);
while (Dep[x] > Dep[y] && Par[x] != Par[y]) {
update(Par[x]), x = Par[x], W.push_back(x);
}
while (Par[x] != Par[y]) {
update(Par[x]); update(Par[y]);
x = Par[x]; y = Par[y];
W.push_back(x); W.push_back(y);
}
while (!W.empty()) {
int u = W.back(); W.pop_back();
if (K[Par[u]] == K[u]) Dp[u] = Dp[Par[u]] + 1;
else Dp[u] = 0;
}
}
ans = max(ans, { Dp[n - c - 1], 1 + c - n });
return -ans.vb;
}
Compilation message
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:24:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
24 | while (V.size() <= E[i]) V.push_back(p++);
| ~~~~~~~~~^~~~~~~
tournament.cpp:25:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
25 | while (V.size() > S[i]) Par[V.back()] = n, V.pop_back();
| ~~~~~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1086 ms |
12512 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
