#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
int tree[4 * N];
int rmq[N][20];
array<int, 2> best[N];
list<int>::iterator to[N];
list<int> l;
int* rnk;
int n;
void cons()
{
for (int i = 0; i < n - 1; i++)
{
rmq[i][0] = rnk[i];
}
for (int j = 1; j < 20; j++)
{
for (int i = 0; i + (1 << j) - 1 < n - 1; i++)
{
rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
}
}
}
int getMax(int from, int to)
{
for (int i = 19; i >= 0; i--)
{
if (from + (1 << i) - 1 <= to)
{
return max(rmq[from][i], rmq[to - (1 << i) + 1][i]);
}
}
return -1;
}
void make(int num, int i, int a, int b, int node)
{
if (a == b)
{
tree[node] = num;
return;
}
int mid =(a + b) / 2;
if (i <= mid) make(num, i, a, mid, node * 2);
if (i > mid) make(num, i, mid + 1, b, node * 2 + 1);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
int kth(int k, int a, int b, int node)
{
if (a == b)
{
if (k == 0) return a;
else return n;
}
int mid = (a + b) / 2;
if (tree[node * 2] > k) return kth(k, a, mid, node * 2);
return kth(k - tree[node * 2], mid + 1, b, node * 2 + 1);
}
int GetBestPosition(int xd, int c, int r, int *K, int *s, int *e) {
n = xd;
rnk = K;
for (int i = 0; i < n; i++)
{
l.push_back(i);
best[i] = {i, 0};
make(1, i, 0, n - 1, 1);
}
int i = 0;
auto it = l.begin();
while (i < n)
{
to[i] = it;
i++;
it++;
}
cons();
for (int i = 0; i < c; i++)
{
int a = s[i];
int b = e[i];
int x = kth(a, 0, n - 1, 1);
int y = kth(b + 1, 0, n - 1, 1) - 1;
int cur = getMax(x, y - 1);
auto it = to[x];
auto cbest = best[x];
//cout << x << " " << y << endl;
it++;
while(it != l.end() && *it <= y)
{
if (best[*it][1] > cbest[1])
{
cbest = best[*it];
}
make(0, *it, 0, n - 1, 1);
it = l.erase(it);
}
if (cur < r)cbest[1]++;
best[x] = cbest;
}
auto res = best[0];
for (int i = 1; i < n; i++)
{
if (best[i][1] > res[1]) res = best[i];
}
//cout << res[1] << endl;
return res[0];
}
/*
5 3 3
1
0
2
4
1 3
0 1
0 1
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1132 KB |
Output is correct |
2 |
Correct |
1 ms |
1132 KB |
Output is correct |
3 |
Correct |
2 ms |
1132 KB |
Output is correct |
4 |
Correct |
1 ms |
1132 KB |
Output is correct |
5 |
Correct |
1 ms |
1132 KB |
Output is correct |
6 |
Correct |
1 ms |
1132 KB |
Output is correct |
7 |
Correct |
1 ms |
1132 KB |
Output is correct |
8 |
Correct |
2 ms |
1132 KB |
Output is correct |
9 |
Correct |
2 ms |
1132 KB |
Output is correct |
10 |
Correct |
1 ms |
1132 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1260 KB |
Output is correct |
2 |
Correct |
5 ms |
1900 KB |
Output is correct |
3 |
Correct |
4 ms |
1772 KB |
Output is correct |
4 |
Correct |
7 ms |
1900 KB |
Output is correct |
5 |
Correct |
6 ms |
1772 KB |
Output is correct |
6 |
Correct |
5 ms |
1900 KB |
Output is correct |
7 |
Correct |
5 ms |
1900 KB |
Output is correct |
8 |
Correct |
5 ms |
1900 KB |
Output is correct |
9 |
Correct |
3 ms |
1772 KB |
Output is correct |
10 |
Correct |
6 ms |
1900 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
49 ms |
8044 KB |
Output is correct |
2 |
Correct |
96 ms |
16620 KB |
Output is correct |
3 |
Correct |
71 ms |
14932 KB |
Output is correct |
4 |
Correct |
123 ms |
16640 KB |
Output is correct |
5 |
Correct |
97 ms |
16108 KB |
Output is correct |
6 |
Correct |
107 ms |
15980 KB |
Output is correct |
7 |
Correct |
103 ms |
16620 KB |
Output is correct |
8 |
Correct |
100 ms |
16620 KB |
Output is correct |
9 |
Correct |
60 ms |
14828 KB |
Output is correct |
10 |
Correct |
67 ms |
14956 KB |
Output is correct |