제출 #56348

#제출 시각아이디문제언어결과실행 시간메모리
56348aquablitz11마상시합 토너먼트 (IOI12_tournament)C++14
0 / 100
92 ms15608 KiB
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; const int N = 100010; const int LN = 18; int n, ptr[N], nxt[N], ft[N]; int get(int x) { ++x; int i = 0, c = 0; for (int j = LN-1; j >= 0; --j) { int ni = i+(1<<j); if (ni <= n && ni-(c+ft[ni]) < x) { i = ni; c += ft[ni]; } } return i; } int skip(int x) { if (nxt[x] == x) return x; return nxt[x] = skip(nxt[x]); } void upd(int i) { nxt[i] = i+1; for (++i; i <= n; i += i&-i) ft[i] += 1; } int cnt; vector<int> G[N*2]; int in[N*2], out[N*2], tick, par[N*2][LN], seg[N*4], dep[N*2]; void dfs(int u, int p) { dep[u] = dep[p]+1; in[u] = tick++; par[u][0] = p; for (int i = 1; i < LN; ++i) par[u][i] = par[par[u][i-1]][i-1]; for (auto v : G[u]) dfs(v, u); out[u] = tick; } void updseg(int p, int x) { for (seg[p += cnt] = x; p > 1; p >>= 1) seg[p>>1] = max(seg[p], seg[p^1]); } int getmax(int l, int r) { int ans = 0; for (l += cnt, r += cnt; l < r; l >>= 1, r >>= 1) { if (l&1) ans = max(ans, seg[l++]); if (r&1) ans = max(ans, seg[--r]); } return ans; } int trylift(int s, int r) { int u = s; for (int i = LN-1; i >= 0; --i) { int v = par[u][i]; if (getmax(in[v], out[v]) == r) u = v; } return dep[s]-dep[u]; } int GetBestPosition(int n, int c, int r, int *K, int *S, int *E) { ::n = n; cnt = n; for (int i = 0; i < n; ++i) ptr[i] = i, nxt[i] = i; nxt[n] = n; for (int i = 0; i < c; ++i) { int s = get(S[i]); int e = get(E[i]); for (int j = s; j <= e; j = skip(j)) { G[cnt].push_back(ptr[j]); if (j != s) { ptr[j] = -1; upd(j); } else { ++j; } } ptr[s] = cnt++; } dfs(cnt-1, cnt-1); updseg(in[0], r); for (int i = 0; i < n-1; ++i) updseg(in[i+1], K[i]); pii ans(trylift(0, r), 0); for (int i = 1; i < n; ++i) { updseg(i, r); updseg(i-1, K[i-1]); ans = max(ans, pii(trylift(i, r), i)); } return ans.first; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...