제출 #420594

#제출 시각아이디문제언어결과실행 시간메모리
420594Aldas25마상시합 토너먼트 (IOI12_tournament)C++14
49 / 100
201 ms28100 KiB
#include <bits/stdc++.h> using namespace std; #define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr) #define FOR(i, a, b) for (int i = (a); i <= (b); i++) #define REP(n) FOR(O, 1, (n)) #define f first #define s second #define pb push_back typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<pii> vii; typedef vector<ll> vl; const int MAXN = 500100; const int MAXK = 30; int n, c,r; int k[MAXN], s[MAXN], e[MAXN]; ll tree[4*MAXN], lazy[4*MAXN][2]; void shift (int id) { if (lazy[id][0] != -1) { ll val = lazy[id][0]; tree[2*id] = val; tree[2*id+1] = val; lazy[2*id][0] = lazy[2*id+1][0] = val; lazy[2*id][1] = lazy[2*id+1][1] = 0; lazy[id][0] = -1; } ll val = lazy[id][1]; tree[2*id] -= val; tree[2*id+1] -= val; lazy[2*id][1] += val; lazy[2*id+1][1] += val; lazy[id][1] = 0; } void upd (int t, int fr, int to, ll val, int id = 1, int le = 0, int ri = n-1) { if (to < le || fr > ri) return; if (fr <= le && ri <= to) { if (t == 0) { tree[id] = val; lazy[id][0] = val; lazy[id][1] = 0; } else { tree[id] -= val; lazy[id][0] = -1; lazy[id][1] += val; } return; } int mid = (le+ri)/2; shift(id); upd(t, fr, to, val, 2*id, le, mid); upd (t, fr, to, val, 2*id+1, mid+1, ri); tree[id] = min(tree[2*id], tree[2*id+1]); } ll get (int p, int id = 1, int le = 0, int ri = n-1) { if (le == ri) return tree[id]; int mid = (le+ri)/2; shift(id); if(p <= mid) return get(p, 2*id, le, mid); else return get(p, 2*id+1, mid+1, ri); } int par[MAXN], mn[MAXN], mx[MAXN]; int repr[MAXN]; int find (int a) {return par[a] = par[a]==a ? a : find(par[a]);} bool same (int a, int b) {return find(a) == find(b);} void unite (int a, int b) { a = find(a), b = find(b); if (a == b) return; par[b] = a; mn[a] = max(mn[a], mn[b]); mx[a] = max(mx[a], mx[b]); } int parentInTree[4*MAXN]; vi adj[MAXN]; int dep[MAXN]; int lift[MAXN][MAXK]; int mxDep = 0; void dfs (int v) { mxDep = max(mxDep, dep[v]); FOR(i, 1, MAXK-1) lift[v][i] = lift[lift[v][i-1]][i-1]; for (int u : adj[v]) { dep[u] = dep[v]+1; lift[u][0] = v; dfs(u); } } int lca (int u, int v) { if (u == v) return u; if (dep[u] > dep[v])swap(u,v); int d = dep[v]-dep[u]; FOR(i, 0, MAXK-1) if (d&(1<<i)) v = lift[v][i]; if (u == v) return u; for (int i = MAXK-1; i >= 0; i--) { if (lift[v][i] != lift[u][i]) { v = lift[v][i]; u = lift[u][i]; } } return lift[v][0]; } int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) { n = N; c = C; r = R; FOR(i, 0, n-1) { k[i] = K[i]; } FOR(i, 0, c-1) { s[i] = S[i]; e[i] = E[i]; } FOR(i, 0, n-1) upd(0, i, i, i); FOR(i, 0, n-1) { par[i] = mn[i] = mx[i] = repr[i] = i; } FOR(i, 0, c-1) { int le = 0, ri = n-1; while (le < ri) { int mid = (le+ri)/2; if (get(mid) >= s[i]) ri = mid; else le = mid+1; } int cr = le; int fr = le, to = le; vi nodes; while (cr <= n-1 && get(cr) <= e[i]) { cr = find(cr); to = mx[cr]; nodes.pb(cr); parentInTree[repr[cr]] = n+i; cr = to+1; } int lst = nodes[0]; //for (int k = 1; k < (int)nodes) for (int x : nodes) unite(lst,x); repr[find(fr)] = n+i; upd(0, fr, to, get(fr)); if (to+1 <= n-1) upd(1, to+1, n-1, e[i]-s[i]); //cout <<" after i=" << i << " round s=" << s[i] << " e=" << e[i] << endl; //FOR(k, 0, n-1) cout << " curval k=" << k << " val = " << get(k) << endl; } // FOR(i, 0, n+c-1) cout << " i = " << i << " par in tree = " << parentInTree[i] << endl; FOR(i, 0, n+c-2) adj[parentInTree[i]].pb(i); dfs(n+c-1); vi wh; FOR(i, 0, n-2) if (k[i] > r) wh.pb(i); /* cout << " white: "; for (int xx : wh) cout << xx << " "; cout << endl;*/ //if ((int)wh.size() == 0) { // return mxDep; // } int ans = 0; int ansId = 0; int whId = -1; FOR(i, 0, n-1) { // cout << " i = " << i << endl; if (whId+1 < (int)wh.size() && wh[whId+1] < i) whId++; /// whId - before, whId+1 - after //cout << " whId = " << whId << endl; int cur = dep[i]; if (whId >= 0) { int anc = lca(wh[whId], i); //cout << " anc wh = " << wh[whId] << " i = " << i << " anc = " << anc << endl; int dst = dep[i] - dep[anc] - 1; cur = min(cur, dst); } if (whId+1 < (int)wh.size()) { // cout << " adaasdass" << endl; //cout << " bef anc wh = " << wh[whId+1]+1 << " i = " << i << endl; int anc = lca(wh[whId+1]+1, i) ; //cout << " anc wh = " << wh[whId+1]+1 << " i = " << i << " anc = " << anc << endl; int dst = dep[i] - dep[anc] - 1; cur = min(cur, dst); } //cout << " i = " << i << " cur = " << cur << endl; if (cur > ans) { ans = cur; ansId = i; } } return ansId; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...