#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
#define all(x) x.begin(), x.end()
#define vf first
#define vs second
const int mod = 998244353;
const int MX = 1000000005;
const int L = 20;
struct Seg
{
int siz;
vector<pair<int, int>> v;
void init(int n)
{
siz = 1;
while (siz < n)
siz *= 2;
v.assign(siz * 2, mp(MX, -1));
}
pair<int, int> merge(pair<int, int> x, pair<int, int> y)
{
pair<int, int> res;
res.vf = min(x.vf, y.vf);
if (x.vf == y.vf)
res.vs = min(x.vs, y.vs);
else if (res.vf == x.vf)
res.vs = x.vs;
else
res.vs = y.vs;
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 mp(MX, -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>> v(n);
for (int i = 0; i < n; i++)
{
cin >> v[i].vf >> v[i].vs;
}
// positions acocrding to sorted e
vector<pair<int, pair<int, int>>> e_sort;
// vector<pair<int,pair<int,int>>> rev;
for (int i = 0; i < n; i++)
{
e_sort.pb(mp(v[i].vs, mp(v[i].vf, i)));
}
sort(all(e_sort));
// rev = e_sort;
// reverse(all(rev));
int pos[n], rev[n];
for (int i = 0; i < n; i++)
{
pos[e_sort[i].vs.vs] = i;
rev[i] = e_sort[i].vs.vs;
}
// segtree
Seg st;
st.init(n + 1);
for (int i = n - 1; i >= 0; i--)
{
st.set(i, mp(e_sort[i].vs.vf, i));
}
// binary lifting
int up[n][L];
int p[n];
for (int i = 0; i < n; i++)
{
pair<int, pair<int, int>> tp = mp(e_sort[i].vs.vf, mp(-1, -1));
int left = (lower_bound(all(e_sort), tp) - e_sort.begin());
if (left == i)
up[i][0] = p[i] = i;
else
{
p[i] = st.range_mx(left, i).vs;
// cout << left << ' ' << st.range_mx(left,i).vf << ' ' << p[i] << '\n';
up[i][0] = p[i];
}
}
for (int j = 1; j < L; j++)
{
for (int i = 0; i < n; i++)
{
if (j == 1)
up[i][j] = up[p[i]][j - 1];
else
up[i][j] = up[up[i][j - 1]][j - 1];
}
}
// answering the queries
while (q--)
{
int s, e;
cin >> s >> e;
s--;
e--;
if (s == e)
{
cout << 0 << '\n';
continue;
}
int ogs = pos[s], oge = pos[e];
if (ogs > oge)
{
if (v[s].vs >= v[e].vf && v[s].vs <= v[e].vs)
{
cout << 1 << '\n';
continue;
}
else
{
cout << "impossible\n";
continue;
}
}
int i = oge;
int mn = v[s].vs;
int ans = 0;
for (int j = L - 1; j >= 0; j--)
{
if (v[rev[up[i][j]]].vf > mn)
{
ans += (1 << j);
i = up[i][j];
}
}
// if (v[rev[i]].vf > mn)
// {
// i = up[i][0];
// ans++;
// }
ans++;
i = up[i][0];
if (v[rev[i]].vf > mn)
cout << "impossible\n";
else
cout << ans << "\n";
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// int t;cin >> t;
// while(t--)
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
75 ms |
17284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
