#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 3e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
mt19937 rng(1);
int n, c, r;
int k[N], s[N], e[N];
int bit[N], cur_comp[N], cnt;
// it works like this:
// we build a tree, n knights, finds lca of the position we want to choose with the nearest left&right
void upd(int id, int val){
for(; id <= n; id += id & -id) bit[id] += val;
}
int find(int k){
int ans = 0;
for(int i = 19; i >= 0; i--){
if((ans + (1LL << i)) > n) continue;
if(bit[ans + (1LL << i)] >= k) continue;
k -= bit[ans + (1LL << i)];
ans += (1LL << i);
}
return ans + 1;
}
vector<int> Adj[N];
int anc[N][20], d[N];
void dfs(int u, int p){
for(auto v : Adj[u]){
if(v == p) continue;
//cout << u << " " << v << "\n";
anc[v][0] = u;
for(int i = 1; i <= 19; i++) anc[v][i] = anc[anc[v][i - 1]][i - 1];
d[v] = d[u] + 1;
dfs(v, u);
}
}
int lca(int x, int y){
if(d[x] > d[y]) swap(x, y);
int diff = d[y] - d[x];
for(int i = 19; i >= 0; i--) if(diff & (1LL << i)) y = anc[y][i];
if(x == y) return x;
for(int i = 19; i >= 0; i--){
if(anc[x][i] != anc[y][i]){
x = anc[x][i], y = anc[y][i];
}
}
return anc[x][0];
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
n = N, c = C, r = R;
for(int i = 1; i <= c; i++){
s[i] = S[i - 1] + 1, e[i] = E[i - 1] + 1;
}
for(int i = 0; i < (n - 1); i++) k[i + 1] = K[i] + 1;
r++;
vector<int> larger;
larger.pb(0);
for(int i = 1; i < n; i++) if(k[i] > r) larger.pb(i);
larger.pb(n);
for(int i = 1; i <= n; i++) upd(i, 1);
int cnt = n;
for(int i = 1; i <= n; i++) cur_comp[i] = i;
for(int i = 1; i <= c; i++){
cnt++;
for(int j = s[i]; j <= e[i]; j++){
int temp = find(j);
Adj[cnt].pb(cur_comp[temp]);
}
for(int j = s[i] + 1; j <= e[i]; j++){
int temp = find(s[i]);
upd(temp, -1);
}
int temp = find(s[i]);
cur_comp[temp] = cnt;
}
dfs(cnt, cnt);
ii answer = {-oo, oo};
for(int pos = 1; pos <= n; pos++){
vector<int>::iterator it = lower_bound(larger.begin(), larger.end(), pos), it2 = it;
it2--;
int mini = oo;
if((*it) < n) mini = min(mini, d[pos] - d[lca(pos, (*it) + 1)] - 1);
if((*it2) > 0) mini = min(mini, d[pos] - d[lca(pos, (*it2))] - 1);
if(mini > answer.fi) answer = {mini, pos};
// cout << mini << " " << pos << "\n";
}
return (answer.se - 1);
// return 0;
}
Compilation message
tournament.cpp:18:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
18 | const int oo = 1e18 + 7, mod = 1e9 + 7;
| ~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7508 KB |
Output is correct |
| 5 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 6 |
Correct |
5 ms |
7500 KB |
Output is correct |
| 7 |
Correct |
4 ms |
7496 KB |
Output is correct |
| 8 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 9 |
Correct |
6 ms |
7368 KB |
Output is correct |
| 10 |
Correct |
4 ms |
7380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 2 |
Correct |
11 ms |
8912 KB |
Output is correct |
| 3 |
Correct |
7 ms |
7892 KB |
Output is correct |
| 4 |
Correct |
10 ms |
8664 KB |
Output is correct |
| 5 |
Correct |
9 ms |
8660 KB |
Output is correct |
| 6 |
Correct |
9 ms |
8276 KB |
Output is correct |
| 7 |
Correct |
10 ms |
8788 KB |
Output is correct |
| 8 |
Correct |
9 ms |
8660 KB |
Output is correct |
| 9 |
Correct |
7 ms |
7892 KB |
Output is correct |
| 10 |
Correct |
12 ms |
8536 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
16908 KB |
Output is correct |
| 2 |
Correct |
128 ms |
38488 KB |
Output is correct |
| 3 |
Correct |
54 ms |
19004 KB |
Output is correct |
| 4 |
Correct |
113 ms |
34180 KB |
Output is correct |
| 5 |
Correct |
113 ms |
34780 KB |
Output is correct |
| 6 |
Correct |
128 ms |
26536 KB |
Output is correct |
| 7 |
Correct |
111 ms |
35548 KB |
Output is correct |
| 8 |
Correct |
115 ms |
35688 KB |
Output is correct |
| 9 |
Correct |
57 ms |
18572 KB |
Output is correct |
| 10 |
Correct |
64 ms |
19080 KB |
Output is correct |
