#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)x.size()
#define ins insert
#define lb lower_bound
template<class T> bool ckmax(T& a, const T& b) {
return a < b ? a = b, 1 : 0; }
/**
* Description: A set (not multiset!) with support for finding the $n$'th
* element, and finding the index of an element. Change \texttt{null\_type} for map.
* Time: O(\log N)
* Source: KACTL
* Verification: many
*/
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>,
rb_tree_tag, tree_order_statistics_node_update>;
#define ook order_of_key
#define fbo find_by_order
void treeExample() {
Tree<int> t, t2; t.insert(8);
auto it = t.insert(10).f; assert(it == t.lb(9));
assert(t.ook(10) == 1 && t.ook(11) == 2 && *t.fbo(0) == 8);
t.join(t2); // assuming T < T2 or T > T2, merge t2 into t
}
/**
int atMost(Tree<pi>& T, int r) {
return T.ook({r,MOD}); }
int getSum(Tree<pi>& T, int l, int r) {
return atMost(T,r)-atMost(T,l-1); }
*/
pi topi[200005];
int par[200005][30];
int curind = 0;
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
Tree<pi> ranges; //[start, ind]
for(int i = 0; i < N; i++){
assert(i == curind);
ranges.ins(mp(i, i));
topi[curind++] = mp(i, i);
}
for(int i = 0; i < C; i++){
// cout << ("Round " + to_string(i) + "\n");
// for(auto u: ranges){
// cout << u.f << " " << u.s << ", ";
// }
// cout << "\n";
auto it1 = ranges.fbo(S[i]);
auto it2 = ranges.fbo(E[i]);
pi np = mp(topi[it1->s].f, topi[it2->s].s); //new range
int nind = curind++;
while(next(it1) != it2){
par[(next(it1))->s][0] = nind;
ranges.erase(next(it1));
}
par[it1->s][0] = nind;
ranges.erase(it1);
par[it2->s][0] = nind;
ranges.erase(it2);
topi[nind] = np;
ranges.ins(mp(np.f, nind));
// for(auto u: ranges){
// cout << u.f << " " << u.s << ", ";
// }
// cout << "\n";
}
assert(sz(ranges) == 1);
par[curind-1][0] = curind;
topi[curind] = mp(-3, N+3);
par[curind][0] = curind;
for(int j = 1; j < 30; j++){
for(int i = 0; i <= curind; i++){
par[i][j] = par[par[i][j-1]][j-1];
}
}
// for(int i = 0; i <= curind; i++){
// cout << i << " " << topi[i].f << " " << topi[i].s << "\n";
// }
// for(int i = 0; i <= curind; i++){
// cout << i << " " << par[i][0] << "\n";
// }
set<int> poses;
poses.ins(-1);
poses.ins(N-1);
for(int i = 0; i < N-1; i++){
if(K[i] > R){
poses.ins(i);
}
}
int ans = 0;
for(int i = 0; i < N; i++){
//cout << ("Test " + to_string(i) + "\n");
//last thing that is < i
//first thing that is >= i, add 1 to that
int l, r;
l = *(prev(poses.lb(i)));
r = *(poses.lb(i))+1;
//cout << l << " " << r << "\n";
int node = i;
int curans = 0;
for(int j = 29; j >= 0; j--){
int nnode = par[node][j];
pi np = topi[nnode];
if(np.f <= l || r <= np.s){
continue;
}
//cout << j << " " << node << " " << nnode << "\n";
node = nnode;
curans+=(1<<j);
}
ckmax(ans, curans);
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
107 ms |
14840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
