// #include "grader.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> AdjList[200005];
int sz[200005];
int curNode = 1;
int N, C, R, *K, *S, *E;
int actualIdxToNode[100005];
int nodeToActualIdx[200005];
struct node {
node *left, *right;
int subtreeSize;
int val;
node(): left(NULL), right(NULL) {subtreeSize = 1; val = -1;};
};
void balance(node *n) {
if(n->left == NULL) return;
if(n->left->subtreeSize * 2 < n->right->subtreeSize) {
node *temp = new node();
temp->left = n->left;
temp->right = n->right->left;
temp->subtreeSize = temp->left->subtreeSize + temp->right->subtreeSize;
n->left = temp;
n->right = n->right->right;
} else if(n->right->subtreeSize * 2 < n->left->subtreeSize) {
node *temp = new node();
temp->right = n->right;
temp->left = n->left->right;
temp->subtreeSize = temp->right->subtreeSize + temp->left->subtreeSize;
n->right = temp;
n->left = n->left->left;
}
}
node* getAtIdx(node *n, int idx, int curIdx) {
if(n->left == NULL) return n;
if(curIdx + n->left->subtreeSize <= idx) {
return getAtIdx(n->right, idx, curIdx+n->left->subtreeSize);
} else {
return getAtIdx(n->left, idx, curIdx);
}
}
void addAtIdx(node *n, int id, int idxToAdd, int curIdx) {
if(n->left==NULL) {
if(n->val == -1) {
n->val = id;
} else {
if(curIdx == idxToAdd) {
n->left = new node();
n->left->val = id;
n->right = new node();
n->right->val = n->val;
n->val = -2;
} else {
n->right = new node();
n->right->val = id;
n->left = new node();
n->left->val = n->val;
n->val = -2;
}
n->subtreeSize = n->left->subtreeSize + n->right->subtreeSize;
}
} else {
if(curIdx + n->left->subtreeSize <= idxToAdd) {
addAtIdx(n->right, id, idxToAdd, curIdx+n->left->subtreeSize);
} else {
addAtIdx(n->left, id, idxToAdd, curIdx);
}
n->subtreeSize = n->left->subtreeSize + n->right->subtreeSize;
}
balance(n);
}
node root = *(new node);
void addNode(int idxToAdd, int sizeToAdd) {
node *temp = getAtIdx(&root, idxToAdd, 0);
if(temp->val==-1) temp->val = 1;
for(int i = 1; i <= sizeToAdd; i++) {
AdjList[temp->val].push_back(curNode+i);
}
temp->val = ++curNode;
for(int i = 1; i < sizeToAdd; i++) {
addAtIdx(&root, ++curNode, idxToAdd+i, 0);
}
}
int curActualIdx = 0;
int depth[200005];
int kthAncestor[20][200005];
void getDepth(int u, int d) {
// cerr << u << ": " << d << endl;
depth[u] = d;
if(AdjList[u].empty()) {
sz[u] = 1;
actualIdxToNode[curActualIdx] = u;
nodeToActualIdx[u] = curActualIdx++;
return;
}
for(auto v: AdjList[u]) {
sz[u] += sz[v];
kthAncestor[0][v] = u;
getDepth(v, d-1);
}
}
void calcKthAncestor() {
kthAncestor[0][1] = 0;
for(int i = 1+1; i <= curNode; i++)
for(int j = 1; j < 20; j++) {
kthAncestor[j][i] = kthAncestor[j-1][kthAncestor[j-1][i]];
if(kthAncestor[j][i]==0) break;
}
}
int lca(int a, int b) {
if(depth[a] < depth[b])
for(int j = 31-__builtin_clz(C-depth[a]); j >= 0; j--)
if(depth[a] + (1<<j) <= depth[b])
a = kthAncestor[j][a];
if(depth[b] < depth[a])
for(int j = 31-__builtin_clz(C-depth[b]); j >= 0; j--)
if(depth[b] + (1<<j) <= depth[a])
b = kthAncestor[j][b];
for(int j = 31-__builtin_clz(C-depth[a]); j >= 0; j--)
if(kthAncestor[j][a] != kthAncestor[j][b]) {
a = kthAncestor[j][a];
b = kthAncestor[j][b];
}
if(a != b) {
a = kthAncestor[0][a];
b = kthAncestor[0][b];
}
return a;
}
int closestToLeft[100005];
int closestToRight[100005];
int GetBestPosition(int N_, int C_, int R_, int *K_, int *S_, int *E_) {
N=N_, C=C_, R=R_;
K=K_, S=S_, E=E_;
sz[1] = 1;
for(int i = C-1; i >= 0; i--) {
addNode(S[i], E[i]-S[i]+1);
}
for(int i = 0; i < N; i++) {
node *temp = getAtIdx(&root, i, 0);
actualIdxToNode[i] = temp->val;
nodeToActualIdx[temp->val] = i;
// cerr << temp->val << " ";
}
// cerr << endl;
getDepth(1,C);
calcKthAncestor();
closestToLeft[0] = -1;
for(int i = 1; i <= N; i++) {
closestToLeft[i] = closestToLeft[i-1];
if(K[i-1] > R)
closestToLeft[i] = i-1;
}
closestToRight[N-1] = -1;
for(int i = N-1-1; i >= 0; i--) {
closestToRight[i] = closestToRight[i+1];
if(K[i+1-1] > R)
closestToRight[i] = i+1;
}
int ans = -1;
int pos = -1;
for(int i = 0; i < N; i++) {
int a = 0;
if(closestToLeft[i] == -1) {
a = C-depth[actualIdxToNode[i]];
} else {
a = depth[lca(actualIdxToNode[i], actualIdxToNode[closestToLeft[i]])]-depth[actualIdxToNode[i]]-1;
}
int b = 0;
if(closestToRight[i] == -1) {
b = C-depth[actualIdxToNode[i]];
} else {
b = depth[lca(actualIdxToNode[i], actualIdxToNode[closestToRight[i]])]-depth[actualIdxToNode[i]]-1;
}
if(min(a,b) > ans) {
ans = min(a,b);
pos = i;
}
}
return pos;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 3 |
Correct |
6 ms |
5248 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5248 KB |
Output is correct |
| 5 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 6 |
Correct |
6 ms |
5168 KB |
Output is correct |
| 7 |
Correct |
7 ms |
5248 KB |
Output is correct |
| 8 |
Correct |
6 ms |
5248 KB |
Output is correct |
| 9 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 10 |
Correct |
6 ms |
5248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5248 KB |
Output is correct |
| 2 |
Correct |
12 ms |
7168 KB |
Output is correct |
| 3 |
Correct |
9 ms |
6068 KB |
Output is correct |
| 4 |
Correct |
13 ms |
6912 KB |
Output is correct |
| 5 |
Correct |
13 ms |
6904 KB |
Output is correct |
| 6 |
Correct |
11 ms |
6144 KB |
Output is correct |
| 7 |
Correct |
13 ms |
7040 KB |
Output is correct |
| 8 |
Correct |
12 ms |
6912 KB |
Output is correct |
| 9 |
Correct |
8 ms |
5760 KB |
Output is correct |
| 10 |
Correct |
12 ms |
6272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
16128 KB |
Output is correct |
| 2 |
Correct |
183 ms |
52092 KB |
Output is correct |
| 3 |
Correct |
78 ms |
25840 KB |
Output is correct |
| 4 |
Correct |
174 ms |
48016 KB |
Output is correct |
| 5 |
Correct |
399 ms |
48120 KB |
Output is correct |
| 6 |
Correct |
170 ms |
27384 KB |
Output is correct |
| 7 |
Correct |
177 ms |
49256 KB |
Output is correct |
| 8 |
Correct |
178 ms |
49628 KB |
Output is correct |
| 9 |
Correct |
70 ms |
25712 KB |
Output is correct |
| 10 |
Correct |
89 ms |
26044 KB |
Output is correct |
