#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 Poll {
ll l, r;
ll ind;
bool st;
Poll(ll _l, ll _r, bool _st, ll i) :l(_l), r(_r), st(_st), ind(i) {}
bool operator<(const Poll& other) const {
ll m1 = (st ? l : r);
ll 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<ll, ll> vl;
Vertex* l, * r;
Vertex(pair<ll, ll> value) :vl(value),l(nullptr),r(nullptr) {}
};
ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 100007;
const ll LG = 23;
ll n, m, k;
vector<Poll>a;
ll ls[N], rs[N];
ll up[N][LG];
Vertex* root = new Vertex({ MOD,MOD });
unordered_map<ll, multiset<pair<ll,ll>>>d;
pair<ll,ll> get_value(Vertex* v) {
if (!v)return { MOD,MOD };
return v->vl;
}
void update(Vertex* v, ll tl, ll tr, ll ind, pair<ll, ll> vl) {
//cout << tl << " " << tr << endl;
//cout << (v->vl.ff) << endl;
if (tl == tr) {
v->vl = vl;
}
else {
ll 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<ll, ll> get_min(Vertex* v, ll tl, ll tr, ll l, ll r) {
if (l > r || !v)return { MOD,MOD };
if (tl == l && tr == r) {
return get_value(v);
}
else {
ll tm = (tl + tr) / 2;
return min(get_min(v->l, tl, tm, l, min(r, tm)),
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 (ll i = 0; i < n; i++) {
ll l, r;
cin >> l >> r;
a.push_back(Poll(l, r, true, i));
a.push_back(Poll(l, r, false, i));
ls[i] = l;
rs[i] = r;
}
sort(a.begin(), a.end());
for (ll 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 (ll i = 0; i < n; i++) {
cout << up[i][0] << " ";
}
cout << endl;*/
for (ll i = 0; i < n; i++) {
for (ll j = 1; j < LG; j++) {
up[i][j] = up[up[i][j - 1]][j - 1];
//cout << up[i][j] << " ";
}
//cout << endl;
}
for (ll i = 0; i < m; i++) {
ll l, r;
cin >> l >> r;
l--, r--;
if (rs[l] > rs[r]) {
cout << "impossible" << endl;
}
else if (ls[up[r][LG - 1]] > rs[l]) {
cout << "impossible" << endl;
}
else if (l == r) {
cout << 0 << endl;
}
else if (rs[l] >= ls[r]) {
cout << 1 << endl;
}
else {
ll res = 0;
for (ll j = LG - 1; j >= 0; j--) {
if (ls[up[r][j]] > rs[l]) {
r = up[r][j];
res += (1ll << j);
}
}
r = up[r][0];
res++;
if (ls[r] <= rs[l] && rs[l] <= rs[r]) {
if (l != r)res++;
cout << res << endl;
}
else {
assert(false);
cout << "impossible\n";
}
}
}
}
/// ---- - -------- ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - -------- ------ -------- -- - - -
Compilation message
events.cpp: In constructor 'Poll::Poll(ll, ll, bool, ll)':
events.cpp:32:7: warning: 'Poll::st' will be initialized after [-Wreorder]
32 | bool st;
| ^~
events.cpp:31:5: warning: 'll Poll::ind' [-Wreorder]
31 | ll ind;
| ^~~
events.cpp:33:2: warning: when initialized here [-Wreorder]
33 | Poll(ll _l, ll _r, bool _st, ll i) :l(_l), r(_r), st(_st), ind(i) {}
| ^~~~
events.cpp: In function 'int main()':
events.cpp:118:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<Poll>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | for (ll i = 0; i < a.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
461 ms |
99948 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 |
1620 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 |
1620 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 |
1620 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
524 ms |
99944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
461 ms |
99948 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
