/*input
8 5
1 2
3 4
1 5
6 7
5 10
10 20
15 20
999999999 1000000000
1 6
1 7
2 4
3 3
5 8
*/
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N, Q;
cin >> N >> Q;
pair<pair<int, int>, int>A[N];
for (int i = 0; i < N; i++)
{
cin >> A[i].first.second >> A[i].first.first;
A[i].second = i;
}
sort(A, A + N);
int p[N];
for (int i = 0; i < N; i++)
p[A[i].second] = i;
int S[N], E[N];
for (int i = 0; i < N; i++)
{
S[i] = A[i].first.second;
E[i] = A[i].first.first;
}
for (int i = 0; i < N; i++)
{
S[i] = (lower_bound(E, E + N, S[i]) - E);
}
// int D[N][N];
// for (int i = 0; i < N; i++)
// for (int j = 0; j < N; j++)
// D[i][j] = N + 10;
vector<int>V;
int pa[N];
for (int j = 0; j < N; j++)
{
if (S[j] >= j)
{
pa[j] = j;
}
else
{
auto it = lower_bound(V.begin(), V.end(), S[j]);
assert(it != V.end());
pa[j] = *it;
}
// pair<int, int>mn = { N + 1, N + 1};
// for (int i = S[j]; i < j; i++)
// {
// mn = min(mn, {S[i], i});
// }
// pa[j] = mn.second;
// for (int i = 0; i < S[j]; i++)
// D[j][i] = D[mn.second][i] + 1;
while (!V.empty() && S[V.back()] > S[j])
V.pop_back();
V.push_back(j);
}
while (Q--)
{
int s, t;
cin >> s >> t;
s = p[s - 1];
t = p[t - 1];
if (s == t)
{
cout << "0\n";
}
else {
if (A[t].first.second <= A[s].first.first && A[s].first.first <= A[t].first.first)
cout << "1\n";
else {
int a = 1;
while (true)
{
if (s >= S[t])
{
cout << a << "\n";
break;
}
if (pa[t] == t)
{
cout << "impossible\n";
break;
}
t = pa[t];
a++;
}
// int k = D[t][s];
// if (k > N)
// cout << "impossible\n";
// else
// cout << k << "\n";
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Execution timed out |
1590 ms |
3672 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1568 ms |
3736 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Execution timed out |
1590 ms |
3672 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
