//≽^•⩊•^≼
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, q; cin >> n >> q;
vector<array<int, 2>> v(n);
vector<vector<int>> g(n);
vector<vector<array<int, 2>>> qu(n);
vector<int> id(n), root, val(n), ans(q, -1), vis(n), c(n);
for(auto &[i, l]: v) cin >> i >> l;
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int i, int j){
return (v[i][1]==v[j][1])?v[i][0]<v[j][0]:v[i][1]<v[j][1];
});
vector<int> el;
for(int i=n-1; i>=0; i--){
if(el.size()){
int s=-1;
int gh = el.size()-1;
for(int j=17; j>=0; j--){
int tmp = (s+(1<<j));
if(tmp >= el.size()) continue;
if(v[el[gh-tmp]][0]>v[id[i]][1]) s = tmp;
}
s++;
// cout<<v[el[s]][0]<<" "<<<v[id[i]][1]<<"\n";
if(s<el.size() && v[el[gh-s]][0]<=v[id[i]][1]){
g[el[gh-s]].push_back(id[i]);
}
else{
root.push_back(id[i]);
}
}
else root.push_back(id[i]);
while(el.size() && v[el.back()][0]>=v[id[i]][0]){
el.pop_back();
}
el.push_back(id[i]);
}
int cnt = 0;
while(q--){
int x, y; cin >> x >> y;
x--; y--;
if(x==y) ans[cnt++]=0;
else
qu[x].push_back({y, cnt++});
}
vector<int> s;
int count=0;
auto dfs =[&](int vv, int p, auto&&dfs)->void{
val[vv]=count;
vis[vv] = 1;
// cout<<vv<<" "<<p<<"\n";
//cerr<<vv<<" "<<count<<"\n";
for(auto [j, i]: qu[vv]){
if(!vis[j]) continue;
// cerr<<i<<" "<<j<<"gg\n";
ans[i] = count-val[j];
cout<<p<<"\n";
// if(i==0)cout<<count<<"\n";
if(c[j]==0)ans[i]++;
}
// cerr<<vv<<" "<<count<<"\n";
// cout<<endl;
for(auto i: g[vv]){
//cout<<v[i][1]<<" "<<v[p][0]<<"\n";
if(v[i][1]<v[p][0]){
c[vv] = 1;
count++;
dfs(i, vv, dfs);
c[vv] = 0;
count--;
}
else{
c[vv]=0;
dfs(i, p, dfs);
}
}
vis[vv] = 0;
};
for(auto i: root) dfs(i, i, dfs);
// cout<<endl;
for(auto j: ans){
if(j!=-1) cout<<1<<"\n";
else cout<<"impossible"<<"\n";
//else cout<<j-1<<"\n";
}
}
Compilation message
events.cpp: In function 'int main()':
events.cpp:36:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | if(tmp >= el.size()) continue;
| ~~~~^~~~~~~~~~~~
events.cpp:42:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | if(s<el.size() && v[el[gh-s]][0]<=v[id[i]][1]){
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
26028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
