Submission #979449

#TimeUsernameProblemLanguageResultExecution timeMemory
979449LOLOLOJousting tournament (IOI12_tournament)C++17
0 / 100
42 ms5856 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; #define f first #define s second #define pb push_back #define ep emplace #define eb emplace_back #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin()) #define mem(f,x) memset(f , x , sizeof(f)) #define sz(x) (int)(x).size() #define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b)) #define mxx *max_element #define mnn *min_element #define cntbit(x) __builtin_popcountll(x) #define len(x) (int)(x.length()) const int N = 1e5 + 10; struct fen{ vector <ll> f; int N; void ass(int n) { N = n + 100; f.assign(N + 1, 0); } void upd(int i, ll x) { for (;i <= N; i += i & (-i)) f[i] += x; } ll get(int i) { ll s = 0; for (; i; i -= i & (-i)) s += f[i]; return s; } }; struct seg{ vector <int> seg, laz; void ass(int n) { seg.assign(n * 4 + 10, 1); laz.assign(n * 4 + 10, -1); } void build(int id, int l, int r) { if (l == r) { seg[id] = 1; return; } int m = (l + r) / 2; build(id * 2, l, m); build(id * 2 + 1, m + 1, r); seg[id] = seg[id * 2] + seg[id * 2 + 1]; } void push(int id) { int t = laz[id]; if (t == 0) { laz[id * 2] = laz[id * 2 + 1] = seg[id * 2] = seg[id * 2 + 1] = 0; } laz[id] = -1; } void upd(int id, int l, int r, int u, int v) { if (l > v || r < u) return; if (l >= u && r <= v) { seg[id] = 0; laz[id] = 0; return; } push(id); int m = (l + r) / 2; upd(id * 2, l, m, u, v); upd(id * 2 + 1, m + 1, r, u, v); seg[id] = seg[id * 2] + seg[id * 2 + 1]; } int find(int id, int l, int r, int k) { if (id == 1 && k == 0) return 0; if (seg[id] < k) return r + 1; if (l == r) return l; if (k == 0) return l; int m = (l + r) / 2; push(id); if (seg[id * 2] < k) return find(id * 2 + 1, m + 1, r, k - seg[id * 2]); return find(id * 2, l, m, k); } }; int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) { int n = N; int c = C; int r = R; set <int> pos, used; for (int i = 1; i < n; i++) { if (K[i - 1] > r) { pos.insert(i); } used.insert(i); } pos.insert(n + 100); used.insert(n); seg st; st.ass(n); st.build(1, 1, n); fen F; F.ass(n + 1); int ans = 0, p = 0; for (int i = 0; i < c; i++) { S[i]++; E[i]++; int k = E[i]; S[i] = st.find(1, 1, n, S[i] - 1) + 1; E[i] = st.find(1, 1, n, E[i] + 1) - 1; st.upd(1, 1, n, S[i], st.find(1, 1, n, k) - 1); if (*pos.lower_bound(S[i]) < E[i]) { auto it = used.lower_bound(S[i]); vector <int> del; while (it != used.end() && *it <= E[i]) { del.pb(*it); it = next(it); } for (auto x : del) { int t = F.get(x); if (ans < t) { ans = t; p = x - 1; } else { if (ans == t) { p = min(p, x - 1); } } used.erase(x); } } F.upd(S[i], 1); F.upd(E[i] + 1, -1); } for (auto x : used) { int t = F.get(x); if (ans < t) { ans = t; p = x - 1; } else { if (ans == t) { p = min(p, x - 1); } } } return p; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...