제출 #642919

#제출 시각아이디문제언어결과실행 시간메모리
642919Farhan_HY마상시합 토너먼트 (IOI12_tournament)C++14
0 / 100
243 ms23348 KiB
#include<bits/stdc++.h> using namespace std; struct seg { vector<int> tree; void init(int n) { tree.resize(4 * n + 4); } void build(int node, int tl, int tr, int val) { if (tr == tl) { tree[node] = val; return; } int mid = (tr + tl) / 2; build(2 * node, tl, mid, val); build(2 * node + 1, mid + 1, tr, val); tree[node] = tree[2 * node] + tree[2 * node + 1]; } void update(int node, int tl, int tr, int idx, int val) { if (tr == tl) { tree[node] = val; return; } int mid = (tr + tl) / 2; if (idx <= mid) update(2 * node, tl, mid, idx, val); else update(2 * node + 1, mid + 1, tr, idx, val); tree[node] = tree[2 * node] + tree[2 * node + 1]; } int getk_thone(int node, int tl, int tr, int t) { if (tr == tl) return tr; int mid = (tr + tl) / 2; if (tree[2 * node] >= t) return getk_thone(2 * node, tl, mid, t); return getk_thone(2 * node + 1, mid + 1, tr, t - tree[2 * node]); } int getSum(int node, int tl, int tr, int l, int r) { if (l <= tl && tr <= r) return tree[node]; if (tr < l || tl > r) return 0; int mid = (tr + tl) / 2; int p1 = getSum(2 * node, tl, mid, l, r); int p2 = getSum(2 * node + 1, mid + 1, tr, l, r); return p1 + p2; } }; set<int> st1, st2; vector<int> open[100005], close[100005], v; seg tree1; // fix segment's left seg tree2; // fix segment's right seg tree3; // index of first lose seg tree4; int a[100005], l[100005], r[100005]; int GetBestPosition(int n, int c, int num, int *k, int *s, int *e) { for(int i = n - 2; i >= 0; i--) a[i + 2] = k[i]; a[1] = num; for(int i = c - 1; i >= 0; i--) l[i + 1] = s[i] + 1, r[i + 1] = e[i] + 1; tree1.init(n); tree2.init(n); tree4.init(n); tree1.build(1, 1, n, 1); tree2.build(1, 1, n, 1); for(int i = 1; i <= n; i++) { st1.insert(i), st2.insert(i); if (a[i] > num) tree4.update(1, 1, n, i, 1); } for(int i = 1; i <= c; i++) { l[i] = tree1.getk_thone(1, 1, n, l[i]); r[i] = tree2.getk_thone(1, 1, n, r[i]); open[l[i]].push_back(i); close[r[i]].push_back(i); auto it = st1.upper_bound(l[i]); while(it != st1.end() && *it <= r[i]) { tree1.update(1, 1, n, *it, 0); int j = *it; st1.erase(it); it = st1.upper_bound(j); } it = st2.lower_bound(l[i]); while(it != st2.end() && *it < r[i]) { tree2.update(1, 1, n, *it, 0); int j = *it; st2.erase(it); it = st2.upper_bound(j); } } tree3.init(c); st1.clear(); int ans = 0, index = 0; for(int i = 1; i <= n; i++) { if (i != 1) { tree4.update(1, 1, n, i, 0); tree4.update(1, 1, n, i - 1, a[i] > num); } for(auto x: open[i]) { tree3.update(1, 1, c, x, 1); if (tree4.getSum(1, 1, n, l[x], r[x])) st1.insert(x); } int idx = c + 1; if (st1.size()) idx = *st1.begin(); int res = tree3.getSum(1, 1, c, 1, idx - 1); if (res > ans) { ans = res; index = i; } for(auto x: close[i]) { tree3.update(1, 1, c, x, 0); if (tree4.getSum(1, 1, n, l[x], r[x])) st1.erase(st1.find(x)); } } return index - 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...