/** vaziat sorati ghermeze **/
#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define Mp make_pair
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
const int N = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 18;
ll pw(ll a , ll b, ll M) { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }
int n, L[N], R[N];
int rmq[LOG][N];
vector < int > Q[N], id[N << 2], seg[N << 2];
void prep(int *arr)
{
for(int i = 0; i < n - 1; i ++) rmq[0][i] = arr[i];
for(int T = 1; T < LOG; T ++)
{
for(int i = 0; i < n - 1; i ++)
{
if((1 << T) + i > n + 1)
{
break;
}
rmq[T][i] = max(rmq[T - 1][i], rmq[T - 1][i + (1 << (T - 1))]);
}
}
}
void merge(int v)
{
int sz1 = SZ(seg[v << 1]), sz2 = SZ(seg[v << 1 | 1]), i = 0, j = 0;
id[v].push_back(0);
while(i < sz1 || j < sz2)
{
if(j == sz2 || (i < sz1 && seg[v << 1][i] < seg[v << 1 | 1][j]))
{
id[v].push_back(id[v].back() + 1);
seg[v].push_back(seg[v << 1][i ++]);
}
else
{
id[v].push_back(id[v].back());
seg[v].push_back(seg[v << 1 | 1][j ++]);
}
}
}
void build(int v = 1, int tl = 0, int tr = n - 1)
{
if(tl == tr)
{
seg[v] = Q[tl];
return;
}
int mid = (tl + tr) >> 1;
build(v << 1, tl, mid), build(v << 1 | 1, mid + 1, tr);
merge(v);
}
int get(int l, int r, int I, int v = 1, int tl = 0, int tr = n - 1) /// [l, r] query onaii ke kamtar mosavi x an ro begu, I andise upper bound v e
{
if(l > tr || r < tl) return 0;
if(l <= tl && tr <= r)
{
return I;
}
int mid = (tl + tr) >> 1;
return get(l, r, id[v][I], v << 1, tl, mid) + get(l, r, I - id[v][I], v << 1 | 1, mid + 1, tr);
}
inline int ask(int left, int right, int d, int up)
{
if(left > right || d > up) return 0;
return get(left, right, upper_bound(all(seg[1]), up) - seg[1].begin()) - get(left, right, upper_bound(all(seg[1]), d - 1) - seg[1].begin());
}
int fen[N];
void add(int i, int x)
{
for(; i < N; i += i & -i) fen[i] += x;
}
int ask(int x) /// x omin element left esh
{
int p = 0, cnt = 0;
for(int T = LOG - 1; ~T; T --)
{
int now = p + (1 << T);
if(now < N && cnt + fen[now] < x)
{
p = now;
cnt += fen[now];
}
}
return p + 1;
}
int GetBestPosition(int _n, int q, int x, int *p, int *l, int *r)
{
n = _n;
vector < pii > vec;
for(int i = 1; i <= n + 3; i ++) add(i, 1);
int BUG = n;
for(int i = 0; i < q; i ++)
{
/*printf("checking\n");
for(int j = 1; j <= BUG + 1; j ++)
{
printf("%d ", ask(j));
}
printf("\n");
*/
BUG -= r[i] - l[i];
int le = ask(l[i] + 1) - 1, ri = ask(r[i] + 2) - 2;
L[i] = le, R[i] = ri;
for(int j = l[i] + 1; j <= r[i]; j ++)
{
///printf("deleting j = %d\n", ask(l[i] + 2));
add(ask(l[i] + 2), -1);
}
Q[le].push_back(ri);
///printf("query i = %d l = %d r = %d\n", i, L[i], R[i]);
}
build();
prep(p);
int tot = 0, ans = 0;
for(int i = 0; i < n; i ++)
{
int d = i - 1, up = i;
for(int T = LOG - 1; ~T; T --)
{
int pos = d - (1 << T) + 1;
if(i && pos >= 0 && rmq[T][pos] < x)
{
d -= 1 << T;
}
pos = up + (1 << T) - 1;
if(i != n - 1 && pos <= n - 2 && rmq[T][up] < x)
{
up += 1 << T;
}
}
d ++;
int cu = ask(d, i, i, up);
if(tot < cu)
{
tot = cu;
ans = i;
}
}
return ans;
}
/*int main()
{
int _n, q, x, p[N], l[N], r[N];
cin >> _n >> q >> x;
for(int i = 0; i < _n - 1; i ++) cin >> p[i];
for(int i = 0; i < q; i ++) cin >> l[i] >> r[i];
cout << GetBestPosition(_n, q, x, p, l, r);
return 0;
}
*/
/** test corner cases(n = 1?) watch for overflow or minus indices **/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
21452 KB |
Output is correct |
| 2 |
Correct |
13 ms |
21452 KB |
Output is correct |
| 3 |
Correct |
14 ms |
21580 KB |
Output is correct |
| 4 |
Correct |
15 ms |
21572 KB |
Output is correct |
| 5 |
Correct |
13 ms |
21452 KB |
Output is correct |
| 6 |
Correct |
17 ms |
21568 KB |
Output is correct |
| 7 |
Correct |
15 ms |
21568 KB |
Output is correct |
| 8 |
Correct |
18 ms |
21572 KB |
Output is correct |
| 9 |
Correct |
16 ms |
21452 KB |
Output is correct |
| 10 |
Correct |
19 ms |
21528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
21628 KB |
Output is correct |
| 2 |
Correct |
32 ms |
22952 KB |
Output is correct |
| 3 |
Correct |
23 ms |
22036 KB |
Output is correct |
| 4 |
Correct |
25 ms |
22860 KB |
Output is correct |
| 5 |
Correct |
23 ms |
22860 KB |
Output is correct |
| 6 |
Correct |
23 ms |
22536 KB |
Output is correct |
| 7 |
Correct |
24 ms |
22840 KB |
Output is correct |
| 8 |
Correct |
23 ms |
22956 KB |
Output is correct |
| 9 |
Correct |
26 ms |
21964 KB |
Output is correct |
| 10 |
Correct |
36 ms |
22988 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
33348 KB |
Output is correct |
| 2 |
Correct |
218 ms |
53088 KB |
Output is correct |
| 3 |
Correct |
160 ms |
33624 KB |
Output is correct |
| 4 |
Correct |
238 ms |
53532 KB |
Output is correct |
| 5 |
Correct |
227 ms |
52544 KB |
Output is correct |
| 6 |
Correct |
275 ms |
46816 KB |
Output is correct |
| 7 |
Correct |
234 ms |
53936 KB |
Output is correct |
| 8 |
Correct |
224 ms |
53968 KB |
Output is correct |
| 9 |
Correct |
105 ms |
32112 KB |
Output is correct |
| 10 |
Correct |
114 ms |
33868 KB |
Output is correct |
