#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define sz(x) int((x).size())
#define fi first
#define se second
#define round asirhq9rthqurtwhqw
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 100005;
struct Round {
int s, e;
} round[MAXN], tmpr[MAXN];
struct Node {
int sz, lastr;
} seg[4 * MAXN];
ii fen[MAXN];
int val[MAXN], tmp[MAXN], P[MAXN][18], posInTree[MAXN], nArr, numRound, R;
void build(int id, int l, int r) {
if(l == r) {
seg[id] = {1, l};
posInTree[l] = id;
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
seg[id] = {seg[id << 1].sz + seg[id << 1 | 1].sz, seg[id << 1 | 1].lastr};
}
void update(int pos) {
int id(posInTree[pos]);
seg[id] = {0, 0};
while(id > 1) {
id >>= 1;
seg[id].sz = seg[id << 1].sz + seg[id << 1 | 1].sz;
seg[id].lastr = max(seg[id << 1].lastr, seg[id << 1 | 1].lastr);
}
}
Node query(int id, int l, int r, int u, int v) {
if(v < l || u > r)
return {0, 0};
if(u <= l && r <= v)
return seg[id];
int mid = (l + r) >> 1;
Node ql = query(id << 1, l, mid, u, v), qr = query(id << 1 | 1, mid + 1, r, u, v);
return {ql.sz + qr.sz, max(ql.lastr, qr.lastr)};
}
int query(int id, int l, int r, int &sz) {
if(!sz)
return 0;
if(seg[id].sz <= sz) {
sz -= seg[id].sz;
return (sz == 0) ? seg[id].lastr : 0;
}
int mid = (l + r) >> 1;
int ql = query(id << 1, l, mid, sz), qr = query(id << 1 | 1, mid + 1, r, sz);
return max(ql, qr);
}
int findFirst(int x) {
int l(1), r(x - 1), answer(x);
while(l <= r) {
int mid = (l + r) >> 1;
if(query(1, 1, nArr, mid, x - 1).sz == 0) {
answer = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return answer;
}
int findLast(int x) {
int l(x + 1), r(nArr), answer(x);
while(l <= r) {
int mid = (l + r) >> 1;
if(query(1, 1, nArr, x + 1, mid).sz == 0) {
answer = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return answer;
}
inline int getMax(int l, int r) {
int log = 31 - __builtin_clz(r - l + 1);
return max(P[l][log], P[r - (1 << log) + 1][log]);
}
int brute(void) {
int maxWin(0), pos(1);
for (int i = 1; i <= nArr; ++i) {
for (int j = 1; j < i; ++j)
tmp[j] = val[j];
tmp[i] = R;
for (int j = i; j < nArr; ++j)
tmp[j + 1] = val[j];
int numWin(0), szNow(nArr);
for (int i = 1; i <= numRound; ++i) {
int s(tmpr[i].s), e(tmpr[i].e), maxp(0);
for (int j = s; j <= e; ++j)
maxp = max(maxp, tmp[j]);
numWin += (maxp == R);
for (int j = e + 1; j <= szNow; ++j)
tmp[s + j - e] = tmp[j];
tmp[s] = maxp;
szNow -= e - s;
}
if(numWin > maxWin) {
maxWin = numWin;
pos = i;
}
}
cout << maxWin << ' ' << pos << '\n';
return pos - 1;
}
void modify(int i, ii v) {
for (; i > 0; i -= i & -i) {
if(fen[i].fi < v.fi || fen[i].fi == v.fi && fen[i].se > v.se)
fen[i] = v;
}
}
ii get(int i) {
ii res = {0, i};
for (; i <= nArr; i += i & -i) {
if(res.fi < fen[i].fi || res.fi == fen[i].fi && res.se > fen[i].se)
res = fen[i];
}
return res;
}
int leftPos[MAXN];
int GetBestPosition(int _N, int _C, int _R, int _K[], int _S[], int _E[]) {
nArr = _N, numRound = _C, R = _R;
for (int i = 1; i < nArr; ++i) {
val[i] = _K[i - 1];
P[i][0] = val[i];
}
for (int i = 1; i <= nArr; ++i)
leftPos[i] = i;
for (int j = 1; (1 << j) < nArr; ++j) {
for (int i = 1; i + (1 << j) - 1 < nArr; ++i)
P[i][j] = max(P[i][j - 1], P[i + (1 << (j - 1))][j - 1]);
}
build(1, 1, nArr);
for (int i = 1; i <= numRound; ++i) {
tmpr[i] = {_S[i - 1] + 1, _E[i - 1] + 1};
int tmp;
//cout << i << ' ' << _S[i - 1] + 1 << ' ' << _E[i - 1] + 1 << ": ";
round[i].s = query(1, 1, nArr, (tmp = _S[i - 1] + 1));
round[i].e = query(1, 1, nArr, (tmp = _E[i - 1] + 1));
//cout << round[i].s << ' ' << round[i].e << '\n';
leftPos[round[i].e] = leftPos[round[i].s];
round[i] = {leftPos[round[i].s], round[i].e};
tmp = _E[i - 1] - _S[i - 1];
int lasty(round[i].e - 1);
while(tmp--) {
int pos = query(1, 1, nArr, round[i].s, lasty).lastr;
update(pos);
}
}
//cout << brute() << '\n';
for (int i = 1; i <= nArr; ++i)
fen[i] = {0, 1e9};
sort(round + 1, round + numRound + 1, [](const Round &a, const Round &b) {
return (a.e != b.e) ? a.e < b.e : a.s > b.s;
});
int maxWin(0), pos(1);
for (int i = 1; i <= numRound; ++i) {
ii res = get(round[i].s);
++res.fi;
modify(round[i].s, res);
//cout << i << ' ' << round[i].s << ' ' << round[i].e << ' ' << res.fi << ' ' << res.se << '\n';
if(getMax(round[i].s, round[i].e - 1) < R) {
if(maxWin < res.fi || maxWin == res.fi && pos > res.se) {
maxWin = res.fi;
pos = res.se;
}
}
}
//cout << maxWin << ' ' << pos << '\n';
return pos - 1;
}
Compilation message
tournament.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
6 | #pragma GCC optimization ("O3")
|
tournament.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
7 | #pragma GCC optimization ("unroll-loops")
|
tournament.cpp: In function 'void modify(int, ii)':
tournament.cpp:159:50: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
159 | if(fen[i].fi < v.fi || fen[i].fi == v.fi && fen[i].se > v.se)
| ^
tournament.cpp: In function 'ii get(int)':
tournament.cpp:167:54: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
167 | if(res.fi < fen[i].fi || res.fi == fen[i].fi && res.se > fen[i].se)
| ^
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:228:52: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
228 | if(maxWin < res.fi || maxWin == res.fi && pos > res.se) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
316 KB |
Output is correct |
| 4 |
Correct |
1 ms |
316 KB |
Output is correct |
| 5 |
Correct |
1 ms |
308 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
316 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1108 KB |
Output is correct |
| 3 |
Correct |
2 ms |
968 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1108 KB |
Output is correct |
| 5 |
Correct |
7 ms |
1012 KB |
Output is correct |
| 6 |
Correct |
6 ms |
980 KB |
Output is correct |
| 7 |
Correct |
8 ms |
1108 KB |
Output is correct |
| 8 |
Correct |
4 ms |
1108 KB |
Output is correct |
| 9 |
Correct |
3 ms |
852 KB |
Output is correct |
| 10 |
Correct |
5 ms |
1108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
7020 KB |
Output is correct |
| 2 |
Correct |
95 ms |
15580 KB |
Output is correct |
| 3 |
Correct |
47 ms |
12528 KB |
Output is correct |
| 4 |
Correct |
98 ms |
15748 KB |
Output is correct |
| 5 |
Correct |
91 ms |
15160 KB |
Output is correct |
| 6 |
Correct |
80 ms |
14488 KB |
Output is correct |
| 7 |
Correct |
92 ms |
15708 KB |
Output is correct |
| 8 |
Correct |
107 ms |
15672 KB |
Output is correct |
| 9 |
Correct |
66 ms |
12324 KB |
Output is correct |
| 10 |
Correct |
42 ms |
12492 KB |
Output is correct |
