#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 100010, LG = 17;
int mx[LG][MAX_N];
// [L, R)
int qry(int l, int r) {
int lg = __lg(r - l);
return max(mx[lg][l], mx[lg][r - (1<<lg)]);
}
// make it 1 based
struct bit {
vector<int> val;
int n;
bit(int _n) : n(_n) {
val.resize(n + 1);
}
void add(int i, int v) {
for (++i;i <= n;i += i&-i)
val[i] += v;
}
int qry(int k) {
++k;
int res = 0;
for (int i = 1<<LG;i;i>>=1)
if ((res | i) <= n && val[res | i] < k)
k -= val[res |= i];
return res;
}
};
struct segset {
// [L, R, V]
set<tuple<int,int,int>> st;
// [L, i], [i+1, R]
void split(int i) {
auto it = st.lower_bound(make_tuple(i+1, -1, -1));
if (it == begin(st)) return; --it;
auto [l, r, v] = *it;
if (r <= i) return;
assert(l <= i && r > i);
st.erase(it);
st.insert(make_tuple(l, i, v));
st.insert(make_tuple(i+1,r,v));
DE(l, i, i+1, r);
}
void modi(int l, int r, int v) {
split(l-1), split(r);
auto it = st.lower_bound(make_tuple(l, -1, -1));
while (it != end(st)) {
auto [sl, sr, sv] = *it;
if (sl > r) break;
it = st.erase(it);
}
DE(l, r, v);
st.insert(make_tuple(l, r, v));
}
int qry(int x) {
auto it = st.lower_bound(make_tuple(x+1, -1, -1));
if (it == begin(st)) return -1; --it;
auto [l, r, v] = *it;
DE(x, l, r);
if (r < x) return -1;
assert(l <= x && r >= x);
return v;
}
};
int nxt[MAX_N], dp[MAX_N];
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
{
set<int> alive;
bit tree(N);
for (int i = 0;i < N;++i) tree.add(i, 1), alive.insert(i);
for (int i = 0;i < C;++i) {
nxt[i] = i;
int &l = S[i], &r = E[i], sz = r - l;
l = tree.qry(l), r = tree.qry(r+1) - 1;
DE(l, r);
for (auto it = next(alive.lower_bound(l));it != end(alive);) {
if (*it > r) break;
tree.add(*it, -1);
it = alive.erase(it);
}
}
for (int i = 0;i < N;++i) mx[0][i] = K[i];
for (int d = 1;1 << d <= N;++d)
for (int i = 0;i < N;++i)
mx[d][i] = max(mx[d-1][i], mx[d-1][ min(N - 1, i + (1<<(d-1))) ]);
}
segset st;
for (int i = C-1;i >= 0;--i) {
int enemy = qry(S[i], E[i]);
if (enemy < R) {
dp[i] = 1;
int p = st.qry(S[i]);
if (p != -1)
dp[i] += dp[p];
// for (int j = i + 1;j < C;++j) {
// if (S[j] <= S[i] && E[j] >= E[i]) {
// dp[i] += dp[j];
// break;
// }
// }
}
st.modi(S[i], E[i], i);
}
int win = 0, pos = 0;
for (int i = 0;i < N;++i) {
int p = st.qry(i);
if (p != -1)
if (chmax(win, dp[p]))
pos = i;
// for (int j = 0;j < C;++j) {
// if (S[j] <= i && E[j] >= i) {
// if (chmax(win, dp[j]))
// pos = i;
// DE(i, dp[j]);
// break;
// }
// }
}
DE(win, pos);
return pos;
}
Compilation message
tournament.cpp: In member function 'void segset::split(int)':
tournament.cpp:52:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
52 | if (it == begin(st)) return; --it;
| ^~
tournament.cpp:52:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
52 | if (it == begin(st)) return; --it;
| ^~
tournament.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
tournament.cpp:59:3: note: in expansion of macro 'DE'
59 | DE(l, i, i+1, r);
| ^~
tournament.cpp: In member function 'void segset::modi(int, int, int)':
tournament.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
tournament.cpp:69:3: note: in expansion of macro 'DE'
69 | DE(l, r, v);
| ^~
tournament.cpp: In member function 'int segset::qry(int)':
tournament.cpp:74:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
74 | if (it == begin(st)) return -1; --it;
| ^~
tournament.cpp:74:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
74 | if (it == begin(st)) return -1; --it;
| ^~
tournament.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
tournament.cpp:76:3: note: in expansion of macro 'DE'
76 | DE(x, l, r);
| ^~
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
tournament.cpp:94:4: note: in expansion of macro 'DE'
94 | DE(l, r);
| ^~
tournament.cpp:92:30: warning: unused variable 'sz' [-Wunused-variable]
92 | int &l = S[i], &r = E[i], sz = r - l;
| ^~
tournament.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
tournament.cpp:140:2: note: in expansion of macro 'DE'
140 | DE(win, pos);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
512 KB |
Output is correct |
| 8 |
Correct |
1 ms |
492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
492 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1004 KB |
Output is correct |
| 3 |
Correct |
3 ms |
876 KB |
Output is correct |
| 4 |
Correct |
8 ms |
1004 KB |
Output is correct |
| 5 |
Correct |
8 ms |
1004 KB |
Output is correct |
| 6 |
Correct |
9 ms |
1004 KB |
Output is correct |
| 7 |
Correct |
8 ms |
1004 KB |
Output is correct |
| 8 |
Correct |
8 ms |
1004 KB |
Output is correct |
| 9 |
Correct |
2 ms |
876 KB |
Output is correct |
| 10 |
Correct |
9 ms |
1004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
6636 KB |
Output is correct |
| 2 |
Correct |
174 ms |
14560 KB |
Output is correct |
| 3 |
Correct |
61 ms |
12652 KB |
Output is correct |
| 4 |
Correct |
188 ms |
14688 KB |
Output is correct |
| 5 |
Correct |
168 ms |
14316 KB |
Output is correct |
| 6 |
Correct |
183 ms |
13164 KB |
Output is correct |
| 7 |
Correct |
175 ms |
14688 KB |
Output is correct |
| 8 |
Correct |
181 ms |
14688 KB |
Output is correct |
| 9 |
Correct |
52 ms |
12396 KB |
Output is correct |
| 10 |
Correct |
64 ms |
12524 KB |
Output is correct |
