Submission #414810

#TimeUsernameProblemLanguageResultExecution timeMemory
414810Lam_lai_cuoc_doiJousting tournament (IOI12_tournament)C++17
100 / 100
90 ms6840 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; constexpr bool typetest = 0; constexpr int N = 1e5 + 5; struct FenwickTree { int a[N]; int n; FenwickTree() { memset(a, 0, sizeof a); } void Update(int p, int v) { for (; p <= n; p += p & -p) a[p] += v; } int Get(int p) { int ans(0); for (; p; p -= p & -p) ans += a[p]; return ans; } int Get(int l, int r) { return Get(r) - Get(l - 1); } } g; struct Segmentree { int st[N * 4], lazy[N * 4]; void Build(int id, int l, int r) { if (l == r) { st[id] = 1; lazy[id] = -1; return; } Build(id << 1, l, (l + r) / 2); Build(id << 1 | 1, (l + r) / 2 + 1, r); st[id] = st[id << 1] + st[id << 1 | 1]; lazy[id] = -1; } void Push(int id, int l, int r) { if (lazy[id] != -1) { int mid = (l + r) / 2; st[id << 1] = (mid - l + 1) * lazy[id]; lazy[id << 1] = lazy[id]; st[id << 1 | 1] = (r - mid) * lazy[id]; lazy[id << 1 | 1] = lazy[id]; lazy[id] = -1; } } void Update(int id, int l, int r, const int &a, const int &b, const int &v) { if (l > b || r < a) return; if (l >= a && r <= b) { st[id] = (r - l + 1) * v; lazy[id] = v; return; } Push(id, l, r); Update(id << 1, l, (l + r) / 2, a, b, v); Update(id << 1 | 1, (l + r) / 2 + 1, r, a, b, v); st[id] = st[id << 1] + st[id << 1 | 1]; } int Find(int id, int l, int r, int v) { while (1) { if (l == r) return l; Push(id, l, r); if (st[id << 1] >= v) { id <<= 1; r = (l + r) / 2; } else { v -= st[id << 1]; id = id << 1 | 1; l = (l + r) / 2 + 1; } } return 0; } } f; int last[N], id[N]; int GetBestPosition(int n, int c, int r, int *k, int *s, int *e) { f.Build(1, 1, n); g.n = n; for (int i = 1; i <= n; ++i) last[i] = i; for (int i = 0; i < c; ++i) { *(s + i) = f.Find(1, 1, n, ++*(s + i)); *(e + i) = last[f.Find(1, 1, n, ++*(e + i))]; //cout << *(s + i) << " " << *(e + i) << "\n"; last[*(s + i)] = *(e + i); f.Update(1, 1, n, *(s + i) + 1, *(e + i), 0); id[i] = i; } sort(id, id + c, [&](const int &x, const int &y) { return *(s + x) < *(s + y) || (*(s + x) == *(s + y) && *(e + x) < *(e + y)); }); int z = c - 1; vector<pair<int, int>> v; priority_queue<pair<int, int>> x; for (int i = 0, j = 0; i < n - 1; ++i) { while (j < n - 1 && (k[i] <= r) == (k[j] <= r)) ++j; if (k[i] <= r) v.emplace_back(i + 1, j + 1); i = j - 1; } reverse(v.begin(), v.end()); for (auto i : v) { while (~z && *(s + id[z]) >= i.first) { x.emplace(*(e + id[z]), *(s + id[z])); --z; } while (x.size() && x.top().first > i.second) x.pop(); while (x.size()) { //cout << x.top().second << " " << x.top().first << "\n"; g.Update(x.top().second, 1); g.Update(x.top().first + 1, -1); x.pop(); } } pair<int, int> u = {0, 0}; for (int i = 1; i <= n; ++i) u = max(u, make_pair(g.Get(i), -(i - 1))); return -u.second; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...