#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include "bits_stdc++.h"
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
using namespace std;
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, srb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
ll const INF = 1e13;
bool compare(pii a, pii b)
{
if (a.f.s==b.f.s) return a.f.f<b.f.f;
return a.f.s<b.f.s;
}
// RMQ
struct node {
int s, e, m;
pi val;
node * l, * r;
node(int S, int E) {
s = S, e = E, m = (s + e) / 2;
val = mp(INF, -1);
if (s != e) {
l = new node(s, m);
r = new node(m + 1, e);
}
}
void update(int X, pi V) {
if (s == e) {val = min(val, V);}
else {
if (X <= m) l -> update(X, V);
else r -> update(X, V);
val = max(val = l -> val, r -> val);
}
}
pi query(int S, int E) {
if (s == S && e == E) return val;
else if (E <= m) return l -> query(S, E);
else if (S >= m + 1) return r -> query(S, E);
else return min(l -> query(S, m), r -> query(m + 1, E));
}
}* root;
// Twok decomp
ll twok[100005][25];
int main()
{
ll n,q, l, r;
input2(n,q);
vector<pii> eve(n);
vector<pi> save(n);
vector<ll> dis;
for (ll i=0; i<n; ++i) {input2(save[i].f, save[i].s); eve[i] = mp(save[i], i); dis.pb(save[i].f), dis.pb(save[i].s);}
discretize(dis);
sort(eve.begin(), eve.end(), compare);
root = new node(0, dis.size()-1);
for (ll i=0; i<n; ++i)
{
ll l = lb(dis.begin(), dis.end(), eve[i].f.f)-dis.begin(), r = lb(dis.begin(), dis.end(), eve[i].f.s)-dis.begin(), ind = eve[i].s;
root->update(r, mp(l, ind));
pi nxt = root->query(l, r);
if (nxt.f>=l) twok[ind][0] = -1;
else twok[ind][0] = nxt.s;
}
for (ll k=1; k<20; ++k)
{
for (ll x = 0; x<n; ++x)
{
if (twok[x][k-1]==-1) twok[x][k]=-1;
else twok[x][k] = twok[twok[x][k-1]][k-1];
}
}
while (q--)
{
input2(l, r);
l--; r--;
ll ans = 0;
if (l==r) {print(0LL, '\n'); continue;}
if (save[l].s>save[r].s){ cout << "impossible" << '\n'; continue;}
if (save[r].f<=save[l].s) {print(1LL, '\n'); continue;}
for (ll i=19; i>=0; --i)
{
if (twok[r][i]==-1) continue;
if (save[twok[r][i]].f<= save[l].s) continue;
r = twok[r][i];
ans += (1LL<<i);
}
if (twok[r][0]==-1) {cout << "impossible" << endl; continue;}
print(ans+2, '\n');
}
return 0;
}
Compilation message
events.cpp: In function 'int main()':
events.cpp:12:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define input2(x, y) scanf("%lld%lld", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
events.cpp:71:2: note: in expansion of macro 'input2'
71 | input2(n,q);
| ^~~~~~
events.cpp:12:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define input2(x, y) scanf("%lld%lld", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
events.cpp:75:26: note: in expansion of macro 'input2'
75 | for (ll i=0; i<n; ++i) {input2(save[i].f, save[i].s); eve[i] = mp(save[i], i); dis.pb(save[i].f), dis.pb(save[i].s);}
| ^~~~~~
events.cpp:12:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define input2(x, y) scanf("%lld%lld", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
events.cpp:97:3: note: in expansion of macro 'input2'
97 | input2(l, r);
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
219 ms |
39036 KB |
Output isn't correct |
| 3 |
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 |
2652 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 |
2652 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 |
2652 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
213 ms |
38996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
219 ms |
39036 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
