/* Author : Mychecksdead */
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD1 (1000000000+7)
#define MOD (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;
struct Dsu{
vector<int> p, s;
Dsu(int n){
p.resize(n+1);
s.resize(n+1, 1);
for(int i = 1; i <= n; ++i) p[i] = i;
}
int find(int v){
if(p[v] == v) return v;
return (p[v] = find(p[v]));
}
void merge(int a, int b){
a = find(a);
b = find(b);
if(a != b){
if(s[a] > s[b]) swap(a, b);
p[a] = b;
s[b] += s[a];
}
}
};
int n, q, t[N], up[N][K], tmin[N];
array<int, 3> a[N], b[N];
vector<int> all;
void build(int l, int r, int k){
if(l==r){
t[k] = 0;
tmin[k] = MOD;
return;
}
int m = (l+r)>>1;
build(l, m, k<<1);
build(m+1, r, k<<1|1);
t[k] = 0;
tmin[k] = MOD;
}
int get(int l, int r, int p, int k){
if(p > r || l > p) return 0;
if(l == r) return t[k];
int m = (l+r)>>1;
return max({t[k], get(l, m, p, k<<1), get(m+1, r, p, k<<1|1)});
}
int getmin(int l, int r, int p, int k){
if(p > r || l > p) return MOD;
if(l == r) return tmin[k];
int m = (l+r)>>1;
return min({tmin[k], getmin(l, m, p, k<<1), getmin(m+1, r, p, k<<1|1)});
}
void update(int l, int r, int ql, int qr, int k, int val){
if(ql > r || l > qr) return;
if(ql <= l && r <= qr){
t[k] = max(val, t[k]);
return;
}
int m = (l+r)>>1;
update(l, m, ql, qr, k<<1, val);
update(m+1, r, ql, qr, k<<1|1, val);
}
void updatemin(int l, int r, int ql, int qr, int k, int val){
if(ql > r || l > qr) return;
if(ql <= l && r <= qr){
tmin[k] = min(val, tmin[k]);
return;
}
int m = (l+r)>>1;
updatemin(l, m, ql, qr, k<<1, val);
updatemin(m+1, r, ql, qr, k<<1|1, val);
}
bool comp(const array<int, 3> &a, const array<int, 3> &b){
if(a[1] != b[1])
return a[1] < b[1];
return a[0] < b[0];
}
void solve(){
cin >> n >> q;
for(int i = 1; i <= n; ++i){
cin >> a[i][0] >> a[i][1];
all.pb(a[i][0]);
all.pb(a[i][1]);
a[i][2] = i;
}
Dsu d(n);
sort(all(all));
unique(all(all));
build(1, 2*n, 1);
for(int i = 1; i <= n; ++i){
a[i][0] = lower_bound(all(all), a[i][0]) - all.begin() + 1;
a[i][1] = lower_bound(all(all), a[i][1]) - all.begin() + 1;
b[i] = a[i];
}
sort(a + 1, a + 1 + n, comp);
for(int i = 1; i <= n; ++i){
update(1, 2*n, a[i][0], a[i][1], 1, i);
updatemin(1, 2*n, a[i][0], a[i][1], 1, i);
b[a[i][2]][2] = i;
}
for(int i = 1; i <= n; ++i){
int p = get(1, 2*n, a[i][1], 1);
d.merge(a[i][2], a[p][2]);
up[i][0] = (p == i ? -1 : p);
}
for(int j = 1; j < K; ++j) for(int i = 1; i <= n; ++i){
int next = up[i][j - 1];
if(next == -1)
up[i][j] = -1;
else
up[i][j] = up[next][j - 1];
}
for(;q--;){
int s, e; cin >> s >> e;
if(s == e) cout << "0\n";
else if(d.find(s) != d.find(e) || b[s][1] > b[e][1]) cout << "impossible\n";
else{
int v = b[s][2], ans = 0;
for(int j = K - 1; j >= 0; --j){
if(up[v][j] != -1 && a[up[v][j]][1] < b[e][0]) v = up[v][j], ans += (1<<j);
}
int last = getmin(1, 2*n, b[e][0], 1);
if(a[last][0] > a[v][1]) cout << "impossible\n";
else cout << ans + 2 << '\n';
}
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int T = 1, aa;
// cin >> T;aa=T;
while(T--){
// cout << "Case #" << aa-T << ": ";
solve();
}
return 0;
}
Compilation message
events.cpp: In function 'int main()':
events.cpp:152:16: warning: unused variable 'aa' [-Wunused-variable]
152 | int T = 1, aa;
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
165 ms |
16820 KB |
Output is correct |
3 |
Correct |
156 ms |
16792 KB |
Output is correct |
4 |
Incorrect |
169 ms |
16788 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
157 ms |
16772 KB |
Output is correct |
2 |
Correct |
192 ms |
16688 KB |
Output is correct |
3 |
Incorrect |
167 ms |
16780 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
165 ms |
16820 KB |
Output is correct |
3 |
Correct |
156 ms |
16792 KB |
Output is correct |
4 |
Incorrect |
169 ms |
16788 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |