#include <bits/stdc++.h>
#define int long long int
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;
const int INF = 1e18;
const int LOGN = 20;
int arr[N];
// pair<int, int> segment_tree[4 * N];
int up[N][LOGN];
int par[N];
// void build(int id, int l, int r)
// {
// if (l == r)
// {
// segment_tree[id] = {arr[l - 1], l - 1};
// return;
// }
// int mid = (l + r) / 2;
// build(2 * id, l, mid);
// build(2 * id + 1, mid + 1, r);
// segment_tree[id] = min(segment_tree[2 * id], segment_tree[2 * id + 1]);
// return;
// }
// pair<int, int> range(int id, int l, int r, int L, int R)
// {
// if (R < l || L > r)
// {
// return {INF, INF};
// }
// if (L <= l && r <= R)
// {
// return segment_tree[id];
// }
// int mid = (l + r) / 2;
// pair<int, int> x = range(2 * id, l, mid, L, R);
// pair<int, int> y = range(2 * id + 1, mid + 1, r, L, R);
// return min(x, y);
// }
struct Seg
{
int siz;
vector<pair<int, int>> v;
void init(int n)
{
siz = 1;
while (siz < n)
siz *= 2;
v.assign(siz * 2, make_pair(INF, -1));
}
pair<int, int> merge(pair<int, int> x, pair<int, int> y)
{
pair<int, int> res;
res.first = min(x.first, y.first);
if (x.first == y.first)
res.second = min(x.second, y.second);
else if (res.first == x.first)
res.second = x.second;
else
res.second = y.second;
return res;
}
void set(int i, pair<int, int> p, int x, int lx, int rx)
{
if (rx - lx == 1)
{
v[x] = merge(p, v[x]);
return;
}
int m = (lx + rx) / 2;
if (i < m)
set(i, p, 2 * x + 1, lx, m);
else
set(i, p, 2 * x + 2, m, rx);
v[x] = merge(v[2 * x + 1], v[2 * x + 2]);
}
void set(int i, pair<int, int> p)
{
set(i, p, 0, 0, siz);
}
pair<int, int> range_mx(int l, int r, int x, int lx, int rx)
{
if (l >= rx || lx >= r)
return make_pair(INF, -1);
if (lx >= l && rx <= r)
return v[x];
int m = (lx + rx) / 2;
return merge(range_mx(l, r, 2 * x + 1, lx, m), range_mx(l, r, 2 * x + 2, m, rx));
}
pair<int, int> range_mx(int l, int r)
{
return range_mx(l, r, 0, 0, siz);
}
};
void solve()
{
int n, q;
cin >> n >> q;
vector<pair<int, int>> v1;
vector<pair<int, pair<int, int>>> v2;
for (int i = 0; i < n; ++i)
{
int l, r;
cin >> l >> r;
v1.push_back({l, r});
v2.push_back({r, {l, i}});
}
int brr[n], crr[n];
sort(v2.begin(), v2.end());
for (int i = 0; i < n; ++i)
{
arr[i] = v2[i].second.first;
brr[v2[i].second.second] = i;
crr[i] = v2[i].second.second;
}
// build(1, 1, n);
Seg st;
st.init(n + 1);
for (int i = n - 1; i >= 0; i--)
{
st.set(i, make_pair(v2[i].second.first, i));
}
for (int i = 0; i < n; ++i)
{
pair<int, pair<int, int>> p = {v2[i].second.first, {-1, -1}};
int it = lower_bound(v2.begin(), v2.end(), p) - v2.begin();
// cout << v2[i].first << ' ' << it << endl;
if (it == i)
{
up[i][0] = par[i] = i;
}
else
{
// auto idx = range(1, 1, n, it + 1, i + 1);
up[i][0] = par[i] = (st.range_mx(it, i)).second;
}
}
for (int j = 1; j < LOGN; ++j)
{
for (int i = 0; i < n; ++i)
{
if (j == 1)
up[i][j] = up[par[i]][j - 1];
else
up[i][j] = up[up[i][j - 1]][j - 1];
// up[j][i] = up[up[j][i - 1]][i - 1];
}
}
while (q--)
{
int s, e;
cin >> s >> e;
if (s == e)
{
cout << 0 << endl;
continue;
}
s--, e--;
int ogs = brr[s], oge = brr[e];
// int sl = v2[s].second.first, sr = v2[s].first;
// int el = v2[e].second.first, er = v2[e].first;
if (s > e)
{
if (v1[s].second >= v1[e].first && v1[s].second <= v1[e].second)
{
cout << 1 << endl;
continue;
}
else
{
cout << "impossible" << endl;
continue;
}
}
int curr = oge;
int ans = 0;
int mn = v1[s].second;
for (int i = LOGN - 1; i >= 0; --i)
{
if (v1[crr[up[curr][i]]].first > mn)
{
ans += (1 << i);
curr = up[curr][i];
}
}
if (v1[crr[curr]].first > mn)
{
ans++;
curr = up[curr][0];
}
ans++;
curr = up[curr][0];
if (v1[crr[curr]].first > mn)
{
cout << "impossible" << endl;
continue;
}
else
{
cout << ans << endl;
}
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// freopen("prime_subtractorization_input.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
int t = 1;
// cin >> t;
for (int tt = 1; tt <= t; ++tt)
{
// cout << "Case #" << tt << ": ";
solve();
}
return 0;
}
Compilation message
events.cpp: In function 'void solve()':
events.cpp:166:13: warning: unused variable 'ogs' [-Wunused-variable]
166 | int ogs = brr[s], oge = brr[e];
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
76 ms |
30984 KB |
Output is correct |
| 3 |
Incorrect |
80 ms |
31300 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
85 ms |
30976 KB |
Output is correct |
| 2 |
Incorrect |
78 ms |
31300 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
76 ms |
30984 KB |
Output is correct |
| 3 |
Incorrect |
80 ms |
31300 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
