#include<bits/stdc++.h>
using namespace std;
int sz=0;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
//cout.tie(0);
int n,m;
cin>>n>>m;
vector<int>allind;
vector<pair<int,int>>all(n);
for(int i=0;i<n;i++){
cin>>all[i].first>>all[i].second;
allind.push_back(all[i].first);
allind.push_back(all[i].second);
}
sort(allind.begin(),allind.end());
allind.resize(unique(allind.begin(),allind.end())-allind.begin());
sz=(int)allind.size();
vector<vector<pair<int,pair<int,int>>>>quer(sz+10);
vector<vector<int>>addy(sz+1);
for(int i=0;i<n;i++){
int p=lower_bound(allind.begin(),allind.end(),all[i].second)-allind.begin();
int pp=lower_bound(allind.begin(),allind.end(),all[i].first)-allind.begin();
addy[p].push_back(pp);
}
vector<int>res(m+10);
for(int i=0;i<m;i++){
int l,r;
cin>>l>>r;
l--;
r--;
int ppp=lower_bound(allind.begin(),allind.end(),all[r].first)-allind.begin();
int p=lower_bound(allind.begin(),allind.end(),all[r].second)-allind.begin();
int pp=lower_bound(allind.begin(),allind.end(),all[l].second)-allind.begin();
quer[p].push_back(make_pair(ppp,make_pair(i,pp)));
if(l==r){
res[i]=2;
}
}
vector<pair<int,int>>v;
vector<int>vv;
for(int i=0;i<sz;i++){
sort(addy[i].rbegin(),addy[i].rend());
sort(quer[i].begin(),quer[i].end());
for(auto x:addy[i]){
while((int)v.size()>0&&v.back().first>=x){
if((int)vv.size()>0&&vv.back()==v.size()){
vv.pop_back();
}
v.pop_back();
}
while(v.size()>1&&v[(int)v.size()-2].second>=x){
if((int)vv.size()>0&&vv.back()==v.size()){
vv.pop_back();
}
v.pop_back();
}
if((int)v.size()!=0&&v.back().second==i){
//hichy;
}
else{
v.push_back(make_pair(x,i));
if((int)v.size()==1||v[(int)v.size()-2].second<v.back().first){
vv.push_back((int)v.size());
}
}
while(quer[i].size()>0&&quer[i].back().first==x){
auto y=quer[i].back();
swap(y.first,y.second.second);
quer[i].pop_back();
if(res[y.second.first]==2){
res[y.second.first]=0;
continue;
}
int z=lower_bound(v.begin(),v.end(),make_pair(y.first+1,-1))-v.begin();
z--;
if(y.first>i||((int)vv.size()>0&&vv.back()>z+1)){
res[y.second.first]=-1;
continue;
}
if(y.first<=i&&y.first>=y.second.second){
res[y.second.first]=1;
continue;
}
//cout<<i<<" "<<allind[i]<<" "<<vv.back()<<" "<<z<<"\n";
res[y.second.first]=1+(int)v.size()-1-z;
if(y.second.second!=v.back().first){
if(z==(int)v.size()-1||((int)v.size()>1&&v[(int)v.size()-2].second<y.second.second)){
res[y.second.first]++;
}
}
}
}
}
for(int i=0;i<m;i++){
if(res[i]==-1){
cout<<"impossible\n";
}
else{
cout<<res[i]<<"\n";
}
}
}
Compilation message
art.cpp: In function 'int main()':
art.cpp:49:35: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | if((int)vv.size()>0&&vv.back()==v.size()){
| ~~~~~~~~~^~~~~~~~~~
art.cpp:55:35: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | if((int)vv.size()>0&&vv.back()==v.size()){
| ~~~~~~~~~^~~~~~~~~~
interface.cpp: In function 'int publish(std::vector<int>)':
interface.cpp:20:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
20 | if(v.size() != N) {
| ~~~~~~~~~^~~~
interface.cpp: In function 'void answer(std::vector<int>)':
interface.cpp:36:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
36 | if(v.size() != N) {
| ~~~~~~~~~^~~~
/usr/bin/ld: /tmp/ccuK8K7K.o: in function `main':
interface.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cczBhPKN.o:art.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccuK8K7K.o: in function `main':
interface.cpp:(.text.startup+0x16): undefined reference to `solve(int)'
collect2: error: ld returned 1 exit status
