#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
/*
N knights
C rounds S[i] - E[i]
R-ranked late knight
K = initial ordering of present knights.
N+C no
*/
int N;
const int maxN = 100'000;
const int logN = 18;
vector<int> BIT(1+maxN, 0);
vector<int> lft(2*maxN);
vector<int> rgt(2*maxN);
vector<int> nxt(maxN), prv(maxN);
vector<int> parent(2*maxN);
vector< vector<int> > anc(2*maxN+1, vector<int>(1+logN, -1));
vector<int> depth(2*maxN+1);
void add(int I, int V)
{
for(int j = I+1; j <= N; j += j&-j)
BIT[j] += V;
}
int prefsum(int I)
{
int res = 0;
for(int j = I+1; j >= 1; j -= j&-j)
res += BIT[j];
return res;
}
void disable(int p)
{
if(0 <= prv[p])
nxt[ prv[p] ] = nxt[p];
if(nxt[p] <= N-1)
prv[ nxt[p] ] = prv[p];
add(p, -1);
}
int lca(int u, int v)
{
if(depth[u] > depth[v]) swap(u, v);
for(int e = logN; e >= 0; e--)
{
if(depth[anc[v][e]] < depth[u])
continue;
v = anc[v][e];
}
if(u == v) return u;
for(int e = logN; e >= 0; e--)
{
if(anc[v][e] == anc[u][e])
continue;
v = anc[v][e];
u = anc[u][e];
}
return anc[u][0];
}
int GetBestPosition(int N_, int C, int R, int *K, int *S, int *E)
{
N = N_;
for(int i = 0; i < N; i++)
{
nxt[i] = i+1;
prv[i] = i-1;
}
for(int i = 1; i < N; i++)
add(i, +1);
// cerr << "resultant array: ";
// for(int i = 0; i < N; i++) cerr << prefsum(i) << ' ';
// cerr << '\n';
for(int i = 0; i < N; i++)
{
lft[i] = rgt[i] = i;
}
for(int c = 0; c < C; c++)
{
// cerr << "\n\n\n";
// cerr << "op: " << S[c] << ' ' << E[c] << '\n';
int lo = 0;
int hi = N-1;
while(lo != hi)
{
int mid = (lo+hi)/2;
if(prefsum(mid) < S[c])
lo = mid+1;
else
hi = mid;
}
int p = lo;
lft[N+c] = p;
for(int r = 1; r <= E[c] - S[c]; r++)
{
p = nxt[p];
disable(p);
// cerr << "disable " << p << '\n';
//
// cerr << "resultant array: ";
// for(int i = 0; i < N; i++) cerr << prefsum(i) << ' ';
// cerr << '\n';
}
rgt[N+c] = nxt[p] - 1;
// cerr << c << ": " << lft[c] << ' ' << rgt[c] << '\n';
}
vector<int> I(N+C);
for(int i = 0; i < N+C; i++) I[i] = i;
sort(I.begin(), I.end(), [] (int p, int q)
{
if(lft[p] != lft[q]) return lft[p] < lft[q];
else return p > q;
});
vector<int> st;
st.push_back(I[0]);
parent[I[0]] = N+C;
anc[I[0]][0] = N+C;
anc[N+C][0] = N+C;
depth[N+C] = -1;
for(int j = 1; j < N+C; j++)
{
int i = I[j];
while(!(lft[st.back()] <= lft[i] && rgt[i] <= rgt[st.back()]))
st.pop_back();
parent[i] = st.back();
anc[i][0] = st.back();
// cerr << "parent " << lft[i] << ' ' << rgt[i] << " = " << lft[parent[i]] << ' ' << rgt[parent[i]] << '\n';
st.push_back(i);
}
for(int i = N+C-1; i >= 0; i--) depth[i] = 1 + depth[parent[i]];
// cerr << "check\n";
for(int e = 1; e <= 18; e++)
{
for(int i = 0; i <= N+C; i++)
{
// cerr << e << ' ' << i << '\n';
anc[i][e] = anc[ anc[i][e-1] ][e-1];
}
}
vector<int> left_recent(N, -1), right_recent(N, -1); //most recent element > R
if(K[0] > R)
left_recent[0] = 0;
// cerr << "??? " << K[0] << ' ' << R << '\n';
// cerr << left_recent[0] << '\n';
for(int i = 1; i < N-1; i++)
{
left_recent[i] = left_recent[i-1];
if(K[i] > R)
left_recent[i] = i;
}
if(K[N-2] > R)
right_recent[N-2] = N-2;
for(int i = N-3; i >= 0; i--)
{
right_recent[i] = right_recent[i+1];
if(K[i] > R)
right_recent[i] = i;
}
int curr_ans;
int best_pos = 0;
if(right_recent[0] == -1)
curr_ans = depth[0];
else
curr_ans = depth[0] - depth[lca(0, right_recent[0]+1)] - 1;
// cerr << "!!!\n";
// cerr << right_recent[0] << ' ' << lca(0, right_recent[0]+1) << '\n';
// cerr << "\n\n\n\n";
// cerr << "0: ans = " << curr_ans << '\n';
for(int i = 1; i < N; i++)
{
int this_res = depth[i];
if(left_recent[i-1] != -1)
this_res = min(this_res, depth[i] - depth[lca(i, left_recent[i-1])] - 1);
if(i <= N-2)
if(right_recent[i] != -1)
this_res = min(this_res, depth[i] - depth[lca(i, right_recent[i]+1)] - 1);
// cerr << left_recent[i-1] << ' ' << right_recent[i]+1 << '\n';
// cerr << "i = " << i << ": " << left_recent[i-1] << '\n';
if(this_res > curr_ans)
{
curr_ans = this_res;
best_pos = i;
}
// cerr << i << ": ans = " << this_res << '\n';
}
// cerr << lft[3] << ' ' << rgt[3] << ' ' << parent[3] << ' ' << parent[parent[3]] << '\n';
// cerr << parent[4] << ' ' << parent[parent[4]] << '\n';
//
// cerr << depth[4] << '\n';
// cerr << left_recent[3] << '\n';
// cerr << lca(4, left_recent[3]) << '\n';
return best_pos;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
18 ms |
28108 KB |
Output is correct |
| 2 |
Correct |
19 ms |
27980 KB |
Output is correct |
| 3 |
Correct |
25 ms |
28084 KB |
Output is correct |
| 4 |
Correct |
23 ms |
28008 KB |
Output is correct |
| 5 |
Correct |
18 ms |
28108 KB |
Output is correct |
| 6 |
Correct |
18 ms |
28108 KB |
Output is correct |
| 7 |
Correct |
18 ms |
28060 KB |
Output is correct |
| 8 |
Correct |
19 ms |
28024 KB |
Output is correct |
| 9 |
Correct |
18 ms |
28108 KB |
Output is correct |
| 10 |
Correct |
18 ms |
28008 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
18 ms |
28048 KB |
Output is correct |
| 2 |
Correct |
24 ms |
28236 KB |
Output is correct |
| 3 |
Correct |
22 ms |
28140 KB |
Output is correct |
| 4 |
Correct |
23 ms |
28148 KB |
Output is correct |
| 5 |
Correct |
23 ms |
28236 KB |
Output is correct |
| 6 |
Correct |
22 ms |
28172 KB |
Output is correct |
| 7 |
Correct |
22 ms |
28236 KB |
Output is correct |
| 8 |
Correct |
22 ms |
28236 KB |
Output is correct |
| 9 |
Correct |
21 ms |
28108 KB |
Output is correct |
| 10 |
Correct |
24 ms |
28268 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
75 ms |
29252 KB |
Output is correct |
| 2 |
Correct |
171 ms |
31144 KB |
Output is correct |
| 3 |
Correct |
100 ms |
29640 KB |
Output is correct |
| 4 |
Correct |
153 ms |
31016 KB |
Output is correct |
| 5 |
Correct |
155 ms |
31036 KB |
Output is correct |
| 6 |
Correct |
145 ms |
30432 KB |
Output is correct |
| 7 |
Correct |
169 ms |
31128 KB |
Output is correct |
| 8 |
Correct |
161 ms |
31052 KB |
Output is correct |
| 9 |
Correct |
92 ms |
29636 KB |
Output is correct |
| 10 |
Correct |
99 ms |
30452 KB |
Output is correct |
