#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;
typedef long long ll;
typedef long double ld;
#define ff first
#define ss second
struct Point {
int l, r;
int ind;
bool st;
Point(int _l, int _r, bool _st, int i) :l(_l), r(_r), st(_st), ind(i) {}
bool operator<(const Point& other) const {
int m1 = (st ? l : r);
int m2 = (other.st ? other.l : other.r);
if (m1 < m2)return true;
if (m1 > m2)return false;
if (st && !other.st)return true;
if (!st && other.st)return false;
return false;
}
};
struct Vertex {
pair<int, int> vl;
Vertex* l, * r;
Vertex(pair<int, int> value) :vl(value),l(nullptr),r(nullptr) {}
};
ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 1000007;
const ll LG = 23;
ll n, m, k;
vector<Point>a;
multiset<pair<int, int>>s;
int ls[N], rs[N];
int up[N][LG];
Vertex* root = new Vertex({ MOD,MOD });
unordered_map<int, multiset<pair<int,int>>>d;
pair<int,int> get_value(Vertex* v) {
if (!v)return { MOD,MOD };
return v->vl;
}
void update(Vertex* v, int tl, int tr, int ind, pair<int, int> vl) {
//cout << tl << " " << tr << endl;
//cout << (v->vl.ff) << endl;
if (tl == tr) {
v->vl = vl;
}
else {
int tm = (tl + tr) / 2;
if (ind <= tm) {
if (!v->l) {
v->l = new Vertex({ MOD,MOD });
}
update(v->l, tl, tm, ind, vl);
}
else {
if (!v->r) {
v->r = new Vertex({ MOD,MOD });
}
update(v->r, tm + 1, tr, ind, vl);
}
v->vl = min(get_value(v->l), get_value(v->r));
}
}
pair<int, int> get_min(Vertex* v, int tl, int tr, int l, int r) {
if (l > r)return { MOD,MOD };
if (tl == l && tr == r) {
return get_value(v);
}
else {
int tm = (tl + tr) / 2;
if (v->l && v->r) {
return min(get_min(v->l, tl, tm, l, min(r, tm)),
get_min(v->r, tm + 1, tr, max(l, tm + 1), r));
}
else if (v->l) {
return get_min(v->l, tl, tm, l, min(r, tm));
}
return get_min(v->r, tm + 1, tr, max(l, tm + 1), r);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) {
int l, r;
cin >> l >> r;
a.push_back(Point(l, r, true, i));
a.push_back(Point(l, r, false, i));
ls[i] = l;
rs[i] = r;
}
sort(a.begin(), a.end());
for (int i = 0; i < a.size(); i++) {
if (a[i].st) {
d[a[i].r].insert({ a[i].l,a[i].ind });
update(root, 0, MOD - 1, a[i].r, *d[a[i].r].begin());
up[a[i].ind][0] = get_min(root, 0, MOD - 1, 0, a[i].r).ss;
}
else {
d[a[i].r].erase(d[a[i].r].find({ a[i].l,a[i].ind }));
if (d[a[i].r].empty())update(root, 0, MOD - 1, a[i].r, { MOD,MOD });
else {
update(root, 0, MOD - 1, a[i].r, *d[a[i].r].begin());
}
}
}
/*for (int i = 0; i < n; i++) {
cout << up[i][0] << " ";
}
cout << endl;*/
for (int i = 0; i < n; i++) {
for (int j = 1; j < LG; j++) {
up[i][j] = up[up[i][j - 1]][j - 1];
//cout << up[i][j] << " ";
}
//cout << endl;
}
for (int i = 0; i < m; i++) {
int l, r;
cin >> l >> r;
l--, r--;
if (rs[l] > rs[r]) {
cout << "impossible" << endl;
}
else if (ls[up[r][LG - 1]] > ls[l]) {
cout << "impossible" << endl;
}
else if (l == r) {
cout << 0 << endl;
}
else if (rs[l] >= ls[r]) {
cout << 1 << endl;
}
else {
int res = 0;
for (int j = LG - 1; j >= 0; j--) {
if (ls[up[r][j]] > rs[l]) {
r = up[r][j];
res += (1 << j);
}
}
res++;
res++;
cout << res << endl;
}
}
}
/// ---- - -------- ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - -------- ------ -------- -- - - -
Compilation message
events.cpp: In constructor 'Point::Point(int, int, bool, int)':
events.cpp:32:7: warning: 'Point::st' will be initialized after [-Wreorder]
32 | bool st;
| ^~
events.cpp:31:6: warning: 'int Point::ind' [-Wreorder]
31 | int ind;
| ^~~
events.cpp:33:2: warning: when initialized here [-Wreorder]
33 | Point(int _l, int _r, bool _st, int i) :l(_l), r(_r), st(_st), ind(i) {}
| ^~~~~
events.cpp: In function 'int main()':
events.cpp:125:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | for (int i = 0; i < a.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
432 ms |
68468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
1164 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
1164 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
1164 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
399 ms |
68368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
432 ms |
68468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
