#include <bits/stdc++.h>
//~ #include "grader.cpp"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree <pair <int, int>, null_type, less <pair <int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int N = 1000001;
int n, c, r, mxd[N], d[N];
bool can[N];
vector <int> v[N];
ordered_set invs;
map <pair <int, int>, int> mp;
int id(pair <int, int> p){
if(mp.find(p) == mp.end()){
int sz = mp.size();
mp[p] = sz;
}
return mp[p];
}
void dfs(int node, int pnode, int dep){
mxd[node] = d[node] = dep;
if(v[node].size() == 0) return;
can[node] = 1;
for(int i = 0 ; i < (int)v[node].size() ; i++){
int cur = v[node][i];
dfs(cur, node, dep + 1);
if(i != (int)v[node].size() - 1 && can[cur] == 1) can[node] = 0;
mxd[node] = max(mxd[node], mxd[cur]);
}
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
n = N;
c = C;
r = R;
for(int i = 0 ; i < n ; i++){
invs.insert({i, i});
id({i, i});
}
for(int i = 0 ; i < c ; i++){
int l = S[i], r = E[i];
assert(r < (int)invs.size());
vector <pair <int, int> > children;
for(int j = 0 ; j < r - l + 1 ; j++){
auto it = invs.find_by_order(l);
children.push_back(*it);
invs.erase(it);
}
l = children[0].first;
r = children.back().second;
for(auto &i : children){
v[id({l, r})].push_back(id(i));
}
invs.insert({l, r});
}
for(int i = 0 ; i < n - 1 ; i++){
if(K[i] > R) can[id({i, i})] = 1;
}
int root = id({0, n - 1});
dfs(root, -1, 0);
int ans = 0;
for(int node = 0 ; node < (int)mp.size() ; node++){
if(can[node]){
ans = max(ans, mxd[node] - d[node]);
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
24064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
205 ms |
32136 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
