#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag,
tree_order_statistics_node_update>
tin;
const int maxn = 100000;
int seg[4 * maxn];
int *arr;
void build(int curin, int curl, int curr) {
if (curl == curr) {
seg[curin] = arr[curl];
return;
}
build(curin * 2 + 1, curl, (curl + curr) / 2),
build(curin * 2 + 2, (curl + curr) / 2 + 1, curr);
seg[curin] = max(seg[curin * 2 + 1], seg[curin * 2 + 2]);
}
int query(int curin, int curl, int curr, int ql, int qr) {
if (curl > qr || curr < ql) return INT_MIN;
if (ql <= curl && curr <= qr) return seg[curin];
return max(query(curin * 2 + 1, curl, (curl + curr) / 2, ql, qr),
query(curin * 2 + 2, (curl + curr) / 2 + 1, curr, ql, qr));
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
for (int i = 0; i < N; i++) tin.insert(make_pair(i, i));
vector<pair<int, int>> vpii;
for (int i = 0; i < C; i++) {
pair<int, int> newone;
newone.first = tin.find_by_order(S[i])->first;
newone.second = tin.find_by_order(E[i])->second;
for (int j = E[i]; j >= S[i]; j--) tin.erase(tin.find_by_order(j));
tin.insert(newone);
vpii.push_back(newone);
}
arr = K;
build(0, 0, N - 2);
int things[maxn + 1];
for (auto [a, b] : vpii) {
int maxi = query(0, 0, N - 2, a, b - 1);
// cout << a << " " << b << " " << maxi << "\n";
if (maxi < R) {
things[a]++;
things[b + 1]--;
}
}
int cur = 0;
int maxi = -1, maxid = -1;
for (int i = 0; i < N; i++) {
cur += things[i];
if (cur > maxi) {
maxi = cur;
maxid = i;
}
}
return maxid;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
600 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
860 KB |
Output is correct |
4 |
Correct |
1 ms |
860 KB |
Output is correct |
5 |
Correct |
1 ms |
860 KB |
Output is correct |
6 |
Correct |
1 ms |
860 KB |
Output is correct |
7 |
Correct |
1 ms |
860 KB |
Output is correct |
8 |
Correct |
1 ms |
856 KB |
Output is correct |
9 |
Correct |
1 ms |
860 KB |
Output is correct |
10 |
Correct |
1 ms |
860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
860 KB |
Output is correct |
2 |
Correct |
4 ms |
1116 KB |
Output is correct |
3 |
Correct |
2 ms |
1116 KB |
Output is correct |
4 |
Correct |
4 ms |
1116 KB |
Output is correct |
5 |
Correct |
4 ms |
1116 KB |
Output is correct |
6 |
Correct |
5 ms |
1356 KB |
Output is correct |
7 |
Correct |
4 ms |
1372 KB |
Output is correct |
8 |
Correct |
4 ms |
1116 KB |
Output is correct |
9 |
Correct |
2 ms |
1116 KB |
Output is correct |
10 |
Correct |
6 ms |
1372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
58 ms |
5840 KB |
Output is correct |
2 |
Incorrect |
138 ms |
10888 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |