#include<bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
ostream& operator<<(ostream &out, string str) {
for(char c : str) out << c;
return out;
}
template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
return out << "(" << p.ST << ", " << p.ND << ")";
}
template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
out << "{";
for(auto it = a.begin(); it != a.end(); it = next(it))
out << (it != a.begin() ? ", " : "") << *it;
return out << "}";
}
void dump() { cerr << "\n"; }
template<class T, class... Ts> void dump(T a, Ts... x) {
cerr << a << ", ";
dump(x...);
}
#ifdef DEBUG
# define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
# define debug(...) false
#endif
template<class T> int size(T && a) { return (int) a.size(); }
using LL = long long;
using PII = pair<int, int>;
struct Tree {
vector<int> tree;
int sz = 1;
Tree(int n) {
while(sz < n) sz *= 2;
tree.resize(sz * 2);
}
void update(int pos, int val) {
tree[pos += sz] = val;
while(pos /= 2)
tree[pos] = tree[pos * 2] + tree[pos * 2 + 1];
}
int query(int k) {
int pos = 1;
while(pos < sz) {
pos *= 2;
if(k >= tree[pos])
k -= tree[pos], pos++;
}
return pos - sz;
}
};
struct JumpPtr {
int LOG = 20;
vector<vector<int>> &graph, jump;
vector<int> par, dep;
void par_dfs(int v) {
for(int u : graph[v]) {
if(u != par[v]) {
par[u] = v;
dep[u] = dep[v] + 1;
par_dfs(u);
}
}
}
JumpPtr(vector<vector<int>> &graph, int root = 0) : graph(graph) {
int n = size(graph);
par.resize(n, -1);
dep.resize(n);
par_dfs(root);
jump.resize(LOG, vector<int>(n));
jump[0] = par;
FOR(i, 1, LOG - 1) REP(j, n)
jump[i][j] = jump[i - 1][j] == -1 ? -1 : jump[i - 1][jump[i - 1][j]];
}
int jump_up(int v, int k) {
for(int i = LOG - 1; i >= 0; i--)
if(k & (1 << i))
v = jump[i][v];
return v;
}
int lca(int a, int b) {
if(dep[a] < dep[b]) swap(a, b);
int delta = dep[a] - dep[b];
a = jump_up(a, delta);
if(a == b) return a;
for(int i = LOG - 1; i >= 0; i--) {
if(jump[i][a] != jump[i][b]) {
a = jump[i][a];
b = jump[i][b];
}
}
return par[a];
}
int dst(int v, int u) {
return dep[v] - dep[u];
}
};
int GetBestPosition(int N, int C, int R, int K[], int S[], int E[]) {
vector<int> node(N);
vector<vector<int>> graph(N + C);
Tree tree(N);
REP(i, N) {
node[i] = i;
tree.update(i, true);
}
REP(i, C) {
int v = N + i;
FOR(j, S[i], E[i]) {
int q = tree.query(j);
int u = node[q];
graph[v].emplace_back(u);
}
for(int j = E[i]; j >= S[i]; j--) {
int q = tree.query(j);
if(j == S[i])
node[q] = v;
else
tree.update(q, false);
}
}
JumpPtr ptr(graph, N + C - 1);
vector<int> larger;
REP(i, N - 1)
if(K[i] > R)
larger.emplace_back(i);
PII ans = {0, -1};
int cur = 0;
REP(i, N) {
int len = 1e9;
if(cur != 0) {
int v = larger[cur - 1];
int lca = ptr.lca(i, v);
len = min(len, ptr.dst(i, lca));
}
if(cur < size(larger)) {
int v = larger[cur] + 1;
int lca = ptr.lca(i, v);
len = min(len, ptr.dst(i, lca));
if(i == v) cur++;
}
ans = max(ans, {len, -i});
}
return -ans.ND;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
512 KB |
Output is correct |
| 2 |
Correct |
10 ms |
2048 KB |
Output is correct |
| 3 |
Correct |
7 ms |
1152 KB |
Output is correct |
| 4 |
Correct |
10 ms |
1792 KB |
Output is correct |
| 5 |
Correct |
9 ms |
1792 KB |
Output is correct |
| 6 |
Correct |
10 ms |
1536 KB |
Output is correct |
| 7 |
Correct |
10 ms |
1920 KB |
Output is correct |
| 8 |
Correct |
10 ms |
1920 KB |
Output is correct |
| 9 |
Correct |
7 ms |
1024 KB |
Output is correct |
| 10 |
Correct |
11 ms |
1792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
12408 KB |
Output is correct |
| 2 |
Correct |
125 ms |
33016 KB |
Output is correct |
| 3 |
Correct |
74 ms |
15632 KB |
Output is correct |
| 4 |
Correct |
126 ms |
31096 KB |
Output is correct |
| 5 |
Correct |
123 ms |
30712 KB |
Output is correct |
| 6 |
Correct |
133 ms |
24184 KB |
Output is correct |
| 7 |
Correct |
126 ms |
31676 KB |
Output is correct |
| 8 |
Correct |
136 ms |
31736 KB |
Output is correct |
| 9 |
Correct |
62 ms |
15080 KB |
Output is correct |
| 10 |
Incorrect |
80 ms |
15480 KB |
Output isn't correct |
