| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 601858 | MohamedFaresNebili | Jousting tournament (IOI12_tournament) | C++14 | 0 ms | 0 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>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
using vi = vector<int>;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb lower_bound
const int oo = 1000 * 1000 * 1000 + 7;
int LOG[5005], SP[5005][15];
vector<int> P;
int query(int i, int j) {
int K = j - i + 1;
return max(SP[i][K], SP[j - (1 << K) + 1][K]);
}
int GetBestPosition(int N, int C, int R,
vector<int> K, vector<int> S, vector<int> E) {
int res = 0, pos = 0; P.resize(N);
for(int l = 0; l < N; l++) P[l] = l;
for(int l = 0; l < C; l++) {
S[l] = lower_bound(P.begin(), P.end(), S[l]) - P.begin();
E[l] = lower_bound(P.begin(), P.end(), E[l] + 1) - P.begin() - 1;
for(int i = S[l]; i <= E[l]; i++) P[i] = S[l];
for(int i = E[l] + 1; i < N; i++) P[i] -= (E[l] - S[l]);
}
LOG[1] = 0;
for(int l = 2; l < N; l++)
LOG[l] = LOG[l / 2] + 1;
for(int l = 0; l < N - 1; l++)
SP[l][0] = K[l];
for(int l = 1; l < 15; l++)
for(int i = 0; i + (1 << l) <= N; i++)
SP[l][i] = max(SP[l][i - 1], SP[l + (1 << (i - 1))][i - 1]);
for(int l = 0; l < N; l++) {
int best = 0;
for(int i = 0; i < C; i++) {
int lo = S[i], hi = E[i];
if(l > hi || l < lo) continue;
int A = -1, B = -1;
if(l > lo) A = query(S[i], l - 1);
if(l < hi) B = query(l, E[i] - 1);
A = max(A, B);
if(A < R) best++;
else break;
}
if(best > res)
res = best, pos = l;
}
return pos;
}