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;
#ifdef LOCAL
#include <debug.h>
#include "grader.cpp"
#endif
#define ft front
#define bk back
#define st first
#define nd second
#define ins insert
#define ers erase
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define bg begin
#define ed end
#define all(x) (x).bg(), (x).ed()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define FSN(i, n) for (int (i) = (n) - 1; (i) >= 0; --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
----------------------------------------------------------------
END OF TEMPLATE
----------------------------------------------------------------
Tran The Bao - ghostwriter
Training for VOI23 gold medal
----------------------------------------------------------------
DIT ME CHUYEN BAO LOC
----------------------------------------------------------------
*/
const int MAXN = 2e5 + 5;
int N, C, R, f[MAXN], r[MAXN], nxt[MAXN][18], maxv[MAXN][18], LOG[MAXN];
pi a[MAXN];
multiset<pi> s;
vpi seg;
void upd(int pos, int v) { ++pos; for (int i = pos; i < MAXN; i += (i & -i)) f[i] += v; }
int lbound(int x) {
int cur = 0, cnt = 0, ans = N + 1;
FSN(i, 18) {
if (cur + (1 << i) >= MAXN) continue;
if (cnt + f[cur + (1 << i)] >= x) ans = min(ans, cur + (1 << i));
else {
cur |= 1 << i;
cnt += f[cur];
}
}
return ans - 1;
}
int getmax(int l, int r) {
if (l > r) return -1;
int len = LOG[r - l + 1];
return max(maxv[l][len], maxv[r - (1 << len) + 1][len]);
}
int getpos(int i, int h) {
FRN(j, 18)
if (h & (1 << j)) {
i = nxt[i][j];
if (i == -1) return i;
}
return i;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
::N = N;
::C = C;
::R = R;
FOR(i, 1, MAXN - 1) LOG[i] = log2(i);
FRN(i, N - 1) maxv[i][0] = K[i];
FOR(j, 1, 17)
FRN(i, N - 1) {
if (i + (1 << j) - 1 >= N - 1) continue;
maxv[i][j] = max(maxv[i][j - 1], maxv[i + (1 << (j - 1))][j - 1]);
}
FRN(i, N) upd(i, 1);
FRN(i, N) {
seg.pb({i, i});
r[i] = i;
s.insert({i, i});
}
FRN(i, C) {
int l = S[i], r = E[i];
int pos = lbound(l + 1);
int maxr = -1;
auto cur = s.lb({pos, -1});
FOR(i, 1, r - l + 1) {
int curv = (*cur).st;
nxt[(*cur).nd][0] = sz(seg);
s.erase(s.lb({curv, -1}));
cur = s.lb({curv, -1});
maxr = max(maxr, ::r[curv]);
}
s.insert({pos, sz(seg)});
nxt[sz(seg)][0] = -1;
seg.pb({pos, maxr});
::r[pos] = maxr;
}
// debug(seg);
// FRN(i, sz(seg)) {
// if (nxt[i][0] != -1) {
// debug(seg[i], seg[nxt[i][0]]);
// }
// }
FOR(j, 1, 17)
FRN(i, sz(seg)) {
int f = nxt[i][j - 1];
if (f == -1) {
nxt[i][j] = -1;
continue;
}
int s = nxt[f][j - 1];
nxt[i][j] = s;
}
int ans = -1, pos = -1;
FRN(i, N) {
int l = 0, r = N, maxx = -1;
WHILE(l <= r) {
int mid = l + (r - l) / 2;
int cur = getpos(i, mid);
if (cur == -1) {
r = mid - 1;
continue;
}
int ln = seg[cur].st, rn = seg[cur].nd;
int maxl = getmax(ln, rn - 1);
if (maxl <= R) {
maxx = mid;
l = mid + 1;
}
else r = mid - 1;
}
if (maxx > ans) {
ans = maxx;
pos = i;
}
}
// debug(ans);
return pos;
}
/*
5 3 3
1
0
2
4
1 3
0 1
0 1
----------------------------------------------------------------
From Benq:
stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
----------------------------------------------------------------
*/
Compilation message (stderr)
tournament.cpp: In function 'int lbound(int)':
tournament.cpp:34:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
34 | #define FSN(i, n) for (int (i) = (n) - 1; (i) >= 0; --(i))
| ^
tournament.cpp:58:5: note: in expansion of macro 'FSN'
58 | FSN(i, 18) {
| ^~~
tournament.cpp: In function 'int getpos(int, int)':
tournament.cpp:33:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
33 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
| ^
tournament.cpp:74:5: note: in expansion of macro 'FRN'
74 | FRN(j, 18)
| ^~~
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:31:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
31 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
tournament.cpp:85:5: note: in expansion of macro 'FOR'
85 | FOR(i, 1, MAXN - 1) LOG[i] = log2(i);
| ^~~
tournament.cpp:33:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
33 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
| ^
tournament.cpp:86:5: note: in expansion of macro 'FRN'
86 | FRN(i, N - 1) maxv[i][0] = K[i];
| ^~~
tournament.cpp:31:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
31 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
tournament.cpp:87:5: note: in expansion of macro 'FOR'
87 | FOR(j, 1, 17)
| ^~~
tournament.cpp:33:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
33 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
| ^
tournament.cpp:88:5: note: in expansion of macro 'FRN'
88 | FRN(i, N - 1) {
| ^~~
tournament.cpp:33:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
33 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
| ^
tournament.cpp:92:5: note: in expansion of macro 'FRN'
92 | FRN(i, N) upd(i, 1);
| ^~~
tournament.cpp:33:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
33 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
| ^
tournament.cpp:93:5: note: in expansion of macro 'FRN'
93 | FRN(i, N) {
| ^~~
tournament.cpp:33:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
33 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
| ^
tournament.cpp:98:5: note: in expansion of macro 'FRN'
98 | FRN(i, C) {
| ^~~
tournament.cpp:31:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
31 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
tournament.cpp:103:9: note: in expansion of macro 'FOR'
103 | FOR(i, 1, r - l + 1) {
| ^~~
tournament.cpp:31:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
31 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
tournament.cpp:121:5: note: in expansion of macro 'FOR'
121 | FOR(j, 1, 17)
| ^~~
tournament.cpp:33:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
33 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
| ^
tournament.cpp:122:5: note: in expansion of macro 'FRN'
122 | FRN(i, sz(seg)) {
| ^~~
tournament.cpp:33:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
33 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
| ^
tournament.cpp:132:5: note: in expansion of macro 'FRN'
132 | FRN(i, N) {
| ^~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
