제출 #959047

#제출 시각아이디문제언어결과실행 시간메모리
959047vjudge1마상시합 토너먼트 (IOI12_tournament)C++17
0 / 100
43 ms16564 KiB
#include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() const int N = 1e5+5; int mx, ans, n, c, p[N], sz[N], rr[N], ll[N], seg[N*4]; pair<int, int> queries[N]; vector<int> higher, lp[N], rp[N]; set<int> st[N]; int findSet(int x) { return (p[x] == x ? x : p[x] = findSet(p[x])); } void unite(int x, int y) { x = findSet(x); y = findSet(y); if (x == y) return; if (sz[x] < sz[y]) swap(x, y); p[y] = x; sz[x] += sz[y]; ll[x] = min(ll[x], ll[y]); rr[x] = max(rr[x], rr[y]); } void build(int p=1, int l=0, int r=n-1) { if (l == r) { seg[p] = c; return; } int mid = (l+r) >> 1; build(p*2, l, mid); build(p*2+1, mid+1, r); seg[p] = min(seg[p*2], seg[p*2+1]); } void update(int pos, int x, int p=1, int l=0, int r=n-1) { if (l == r) { seg[p] = x; return; } int mid = (l+r) >> 1; if (pos <= mid) update(pos, x, p*2, l, mid); else update(pos, x, p*2+1, mid+1, r); seg[p] = min(seg[p*2], seg[p*2+1]); } int query(int x, int y, int p=1, int l=0, int r=n-1) { if (x > y || y < l || r < x) return c; else if (x <= l && r <= y) { return seg[p]; } int mid = (l+r) >> 1; return min(query(x, y, p*2, l, mid), query(x, y, p*2+1, mid+1, r)); } int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) { mx = ans = 0; n = N; c = C; for (int i = 0; i < n; i++) { p[i] = i; sz[i] = 1; ll[i] = rr[i] = i; } for (int i = 0; i < n-1; i++) { if (K[i] > R) higher.push_back(i); } for (int i = 0; i < c; i++) { int x = E[i]-S[i]; int y = S[i]; while (x--) { y = rr[findSet(y)]; unite(y, y+1); } int nwR = rr[findSet(S[i])]; queries[i] = make_pair(S[i], nwR); lp[S[i]].push_back(i); rp[nwR].push_back(i); //cerr << i << " " << S[i] << " " << nwR << endl; } build(); // pongo todo a c for (int i = 0; i < n; i++) { /* cuantas batallas gano poniendolo en i? miro el mas cercano por cada lado que me gana y cojo la primera query que me toca y que llega mas lejos que ellos con query de minimo en rango */ for (int& j : lp[i]) { st[i].insert(j); st[queries[j].second].insert(j); update(i, *st[i].begin()); update(i, *st[queries[j].second].begin()); } auto it = lower_bound(all(higher), i); int x = (it == higher.begin() ? -1 : *prev(it)); int y = (it == higher.end() ? n-1 : *it) + 1; int nwMx = min(query(0, x), query(y, n-1)); if (nwMx > mx) { mx = nwMx; ans = i; } for (int& j : rp[i]) { st[i].erase(j); st[queries[j].first].erase(j); update(i, (st[i].empty() ? c : *st[i].begin())); update(i, (st[queries[j].first].empty() ? c : *st[queries[j].first].begin())); } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...