| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1111841 | hungnt | Jousting tournament (IOI12_tournament) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define BIT(x, k) (((x) >> (k)) & 1)
#define on(x, k) ((x) ^ (1ll << (k)))
#define pii pair<int, int>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define ll long long
using namespace std;
const int N = 200005;
int n, ro, point;
vector<int> adj[N];
int a[N], bit[N], pa[N], h[N], par[20][N];
int pre[N], suf[N];
int numNode;
void update(int x, int v)
{
for(; x <= n; x += x & -x) bit[x] += v;
}
int Find_pos(int v)
{
int sum = 0;
int pos = 0;
for(int i= __lg(n); i>= 0; i--)
{
if(pos + (1 << i) < n && sum + bit[pos + (1 << i)] < v)
{
sum += bit[pos + (1 << i)];
pos += (1 << i);
}
}
return pos + 1; // +1 because 'pos' will have position of largest value less than 'v'
}
int Find_par(int u)
{
if(u == pa[u]) return u;
return pa[u] = Find_par(pa[u]);
}
void Union(int u, int v)
{
u = Find_par(u), v = Find_par(v);
if(u == v) return;
if(u < v) swap(u, v);
pa[v] = u;
}
void init()
{
cin >> n >> ro >> point;
for(int i = 1; i < n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) update(i, 1);
for(int i = 1; i <= n + n; i++) pa[i] = i;
int l, r;
vector<int> pos;
numNode = n;
while(ro--)
{
cin >> l >> r;
pos.clear();
numNode++;
for(int i = l; i <= r; i++)
{
int p = Find_pos(i);
pos.push_back(p);
}
for(int x : pos)
{
update(x, -1);
x = Find_par(x);
adj[numNode].push_back(x);
}
update(pos[0], 1);
Union(pos[0], numNode);
}
}
void dfs(int u, int p)
{
par[0][u] = p;
for(int v : adj[u])
if(v != p)
{
h[v] = h[u] + 1;
dfs(v, u);
}
}
void build_lca()
{
dfs(numNode, 0);
for(int i = 1; (1 << i) <= n; i++)
for(int j = 1; j <= n; j++)
par[i][j] = par[i - 1][par[i - 1][j]];
}
int lca(int u, int v)
{
if(h[u] < h[v]) swap(u, v);
int dist = h[u] - h[v];
while (dist)
{
u = par[__builtin_ctz(dist)][u];
dist -= dist & -dist;
}
if(u == v) return n;
for(int i = __lg(n); i >= 0; i--)
if(par[i][u] != par[i][v])
{
u = par[i][u];
v = par[i][v];
}
return par[0][u];
}
void process()
{
build_lca();
for (int i = 2; i <= n; i++) pre[i] = (a[i - 1] > point ? i - 1 : pre[i - 1]);
for (int i = n - 1; i >= 1; i--) suf[i] = (a[i] > point ? i + 1 : suf[i + 1]);
pair <int, int> res = {0, -1};
for (int i = 1; i <= n; i++)
{
int f = h[i];
if (pre[i]) f = min(f, h[i] - h[lca(pre[i], i)]);
if (suf[i]) f = min(f, h[i] - h[lca(suf[i], i)]);
res = max(res, make_pair(f, -i));
}
cout << -res.se;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define TASK "tournament"
if (fopen(TASK".INP", "r"))
{
freopen(TASK".INP", "r", stdin);
freopen(TASK".OUT", "w", stdout);
}
init();
process();
cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
}