#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
typedef long long llong;
const int MAXN = 100000 + 10;
const int MAXLOG = 17;
int n, q;
int rank;
int a[MAXN];
int l[MAXN];
int r[MAXN];
int par[MAXN];
int first[MAXN];
int leftFrom[MAXN];
struct BIT
{
int tree[MAXN];
void update(int idx, int val)
{
for (int pos = idx ; pos <= n ; pos += pos & (-pos))
{
tree[pos] += val;
}
}
int findKth(int k)
{
int pos = 0;
for (int log = MAXLOG - 1 ; log >= 0 ; --log)
{
if (pos + (1 << log) <= n && tree[pos + (1 << log)] < k)
{
pos += (1 << log);
k -= tree[pos];
}
}
return pos + 1;
}
};
struct SegmentTree
{
int tree[4*MAXN];
int vals[MAXN];
int cmp(int x, int y)
{
if (vals[x] > vals[y]) return x;
return y;
}
void build(int l, int r, int node)
{
if (l == r)
{
tree[node] = l;
return;
}
int mid = (l + r) / 2;
build(l, mid, 2*node);
build(mid + 1, r, 2*node + 1);
tree[node] = cmp(tree[2*node], tree[2*node + 1]);
}
void update(int l, int r, int node, int queryPos, int queryVal)
{
if (l == r)
{
vals[l] = queryVal;
return;
}
int mid = (l + r) / 2;
if (queryPos <= mid) update(l, mid, 2*node, queryPos, queryVal);
else update(mid + 1, r, 2*node + 1, queryPos, queryVal);
tree[node] = cmp(tree[2*node], tree[2*node + 1]);
}
int query(int l, int r, int node, int queryL, int queryR)
{
if (queryL <= l && r <= queryR)
{
return tree[node];
}
int res = 0;
int mid = (l + r) / 2;
if (queryL <= mid) res = cmp(res, query(l, mid, 2*node, queryL, queryR));
if (mid + 1 <= queryR) res = cmp(res, query(mid + 1, r, 2*node + 1, queryL, queryR));
return res;
}
void build()
{
for (int i = 1 ; i <= n ; ++i)
{
vals[i] = a[i];
}
build(1, n, 1);
}
void update(int pos, int val)
{
update(1, n, 1, pos, val);
}
int findMAX(int l, int r)
{
return vals[query(1, n, 1, l, r)];
}
};
BIT fenwick;
SegmentTree tree;
struct SparseLift
{
int sparse[MAXLOG][MAXN];
void build(int vals[])
{
for (int i = 1 ; i <= q ; ++i)
{
sparse[0][i] = vals[i];
}
for (int log = 1 ; (1 << log) <= q ; ++log)
{
for (int i = 1 ; i <= q ; ++i)
{
sparse[log][i] = sparse[log - 1][sparse[log - 1][i]];
}
}
}
int lift(int idx)
{
if (tree.findMAX(l[idx], r[idx]) > rank)
{
return 0;
}
int res = 1;
for (int log = MAXLOG - 1 ; log >= 0 ; --log)
{
if (sparse[log][idx] != 0 && tree.findMAX(l[sparse[log][idx]], r[sparse[log][idx]]) <= rank)
{
res += (1 << log);
idx = sparse[log][idx];
}
}
return res;
}
};
SparseLift sparseLift;
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
n = N;
q = C;
rank = R + 1;
for (int i = 1 ; i < n ; ++i)
{
a[i] = K[i - 1] + 1;
fenwick.update(i, 1);
}
a[n] = rank;
fenwick.update(n, 1);
tree.build();
for (int i = 1 ; i <= q ; ++i)
{
int currL = S[i - 1] + 1;
int currR = E[i - 1] + 1;
int searchL = fenwick.findKth(currL);
int searchR = fenwick.findKth(currR);
if (leftFrom[searchL] != 0)
{
searchL = l[leftFrom[searchL]];
}
if (leftFrom[searchR] != 0)
{
searchR = r[leftFrom[searchR]];
}
for (int j = 0 ; j < currR - currL + 1 ; ++j)
{
int curr = fenwick.findKth(currL);
if (first[curr] == 0) first[curr] = i;
else
{
par[leftFrom[curr]] = i;
}
fenwick.update(curr, -1);
}
l[i] = searchL;
r[i] = searchR;
leftFrom[l[i]] = i;
fenwick.update(l[i], 1);
}
sparseLift.build(par);
int ans = sparseLift.lift(first[n]);
int pos = n;
for (int i = n ; i > 1 ; --i)
{
tree.update(i, a[i - 1]);
tree.update(i - 1, rank);
int curr = sparseLift.lift(first[i - 1]);
if (curr >= ans)
{
pos = i - 1;
ans = curr;
}
}
return pos - 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
316 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
312 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
7 ms |
980 KB |
Output is correct |
| 3 |
Correct |
4 ms |
580 KB |
Output is correct |
| 4 |
Correct |
6 ms |
980 KB |
Output is correct |
| 5 |
Correct |
6 ms |
852 KB |
Output is correct |
| 6 |
Correct |
6 ms |
776 KB |
Output is correct |
| 7 |
Correct |
8 ms |
992 KB |
Output is correct |
| 8 |
Correct |
8 ms |
964 KB |
Output is correct |
| 9 |
Correct |
3 ms |
468 KB |
Output is correct |
| 10 |
Correct |
6 ms |
988 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
4540 KB |
Output is correct |
| 2 |
Correct |
179 ms |
13484 KB |
Output is correct |
| 3 |
Correct |
109 ms |
4468 KB |
Output is correct |
| 4 |
Correct |
206 ms |
13524 KB |
Output is correct |
| 5 |
Correct |
209 ms |
13076 KB |
Output is correct |
| 6 |
Correct |
133 ms |
10060 KB |
Output is correct |
| 7 |
Correct |
232 ms |
13500 KB |
Output is correct |
| 8 |
Correct |
195 ms |
13520 KB |
Output is correct |
| 9 |
Correct |
47 ms |
3916 KB |
Output is correct |
| 10 |
Correct |
49 ms |
4716 KB |
Output is correct |
