| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1043718 | Sharky | Jousting tournament (IOI12_tournament) | C++17 | 24 ms | 3888 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 100008;
int fen[N];
void upd(int i, int k) {
for (; i < N; i += (i & -i)) fen[i] += k;
}
int query(int i) {
int res = 0;
for (; i; i -= (i & -i)) res += fen[i];
return res;
}
int GetBestPosition(int n, int k, int rk, int *tmp, int *lb, int *rb) {
vector<int> S(k), E(k);
vector<vector<int>> rng(n+1);
vector<int> a(n+1), nxt(n+1, n), lst(n+1, 0), diff(n+1, 0);
for (int i = 1; i <= n; i++) {
if (i < n) a[i] = tmp[i - 1];
upd(i, 1);
}
for (int i = 0; i < k; i++) {
vector<int> g;
lb[i]++, rb[i]++;
for (int j = lb[i]; j <= rb[i]; j++) {
int l = 1, r = n;
while (l < r) {
int mid = (l + r) >> 1;
if (query(mid) >= j) r = mid;
else l = mid + 1;
}
g.push_back(l);
}
S[i] = g.front();
E[i] = g.back();
rng[S[i]].push_back(E[i]);
for (int j = 1; j < (int) g.size(); j++) upd(g[j], -1);
}
for (int i = n - 1; i >= 1; i--) {
if (a[i] > rk) nxt[i] = i;
else nxt[i] = nxt[i + 1];
}
for (int i = 1; i <= n - 1; i++) {
if (a[i] > rk) lst[i] = i;
else lst[i] = lst[i - 1];
}
int prv = -1, mx = -1, ans;
for (int i = 1; i <= n; i++) {
int l = lst[i - 1] + 1, r = nxt[i];
if (l != prv) {
for (int j = l; j <= r; j++) {
for (auto x : rng[j]) {
if (x <= r) {
diff[j]++;
diff[x+1]--;
}
}
}
for (int j = l+1; j <= r; j++) diff[j] += diff[j - 1];
prv = l;
}
if (diff[i] > mx) mx = diff[i], ans = i;
}
return ans - 1;
}Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
