#include <algorithm>
#include <vector>
#include <map>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define F first
#define S second
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> os;
typedef pair<int, int> ii;
int* arr;
struct seg {
int s, e, m, v;
seg *l, *r;
seg(int _s, int _e) {
s = _s, e = _e, m = (s + e) / 2;
if (s != e) {
l = new seg(s, m);
r = new seg(m + 1, e);
v = max(l -> v, r -> v);
} else v = arr[s];
}
int query(int a, int b) {
if (s == a && e == b) return v;
if (a > m) return r -> query(a, b);
if (b <= m) return l -> query(a, b);
return max(l -> query(a, m), r -> query(m + 1, b));
}
} *root;
vector<int> adjlist[199999];
ii range[199999];
void dfs(int v) {
if (adjlist[v].size() != 0) {
range[v] = ii(100000, -1);
for (int i: adjlist[v]) dfs(i);
for (int i: adjlist[v]) range[v].F = min(range[v].F, range[i].F), range[v].S = max(range[v].S, range[i].S);
} else range[v] = ii(v, v);
}
ii dp(int v, int R) {
if (adjlist[v].size() != 0) {
ii ans = ii(-100000, 1);
for (int i: adjlist[v]) ans = max(ans, dp(i, R));
if (root -> query(range[v].F, range[v].S - 1) < R) ++ans.F;
return ans;
} else return ii(0, -v);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
os sets;
map<int, int> mp;
for (int i = 0; i < N; ++i) sets.insert(i);
for (int i = 0; i < N; ++i) mp[i] = i;
for (int i = 0; i < C; ++i) {
int x = *sets.find_by_order(S[i]);
adjlist[N + i].push_back(mp[x]);
for (int j = S[i]; j < E[i]; ++j) {
os::iterator it = sets.find_by_order(S[i] + 1);
adjlist[N + i].push_back(mp[*it]);
sets.erase(it);
}
mp[x] = N + i;
}
arr = K;
root = new seg(0, N - 2);
dfs(N + C - 1);
return -dp(N + C - 1, R).S;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
4992 KB |
Output is correct |
2 |
Correct |
7 ms |
4992 KB |
Output is correct |
3 |
Correct |
8 ms |
5120 KB |
Output is correct |
4 |
Correct |
8 ms |
5248 KB |
Output is correct |
5 |
Correct |
7 ms |
5120 KB |
Output is correct |
6 |
Correct |
9 ms |
5120 KB |
Output is correct |
7 |
Correct |
8 ms |
5248 KB |
Output is correct |
8 |
Correct |
8 ms |
5120 KB |
Output is correct |
9 |
Correct |
7 ms |
5120 KB |
Output is correct |
10 |
Correct |
8 ms |
5120 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
5248 KB |
Output is correct |
2 |
Correct |
15 ms |
6912 KB |
Output is correct |
3 |
Correct |
11 ms |
5888 KB |
Output is correct |
4 |
Correct |
14 ms |
6272 KB |
Output is correct |
5 |
Correct |
14 ms |
6528 KB |
Output is correct |
6 |
Correct |
16 ms |
6016 KB |
Output is correct |
7 |
Correct |
14 ms |
6656 KB |
Output is correct |
8 |
Correct |
14 ms |
6400 KB |
Output is correct |
9 |
Correct |
11 ms |
5760 KB |
Output is correct |
10 |
Correct |
16 ms |
6144 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
111 ms |
14840 KB |
Output is correct |
2 |
Correct |
238 ms |
42272 KB |
Output is correct |
3 |
Correct |
140 ms |
21624 KB |
Output is correct |
4 |
Correct |
210 ms |
31864 KB |
Output is correct |
5 |
Correct |
208 ms |
35192 KB |
Output is correct |
6 |
Correct |
257 ms |
23928 KB |
Output is correct |
7 |
Correct |
219 ms |
35320 KB |
Output is correct |
8 |
Correct |
219 ms |
35448 KB |
Output is correct |
9 |
Correct |
126 ms |
21496 KB |
Output is correct |
10 |
Correct |
153 ms |
21496 KB |
Output is correct |