This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MAXN=(1<<18), LOG=17, INF=1e9;
int tree[2*MAXN-1];
int find(int x, int l, int r, int lt, int rt)
{
if (l>=rt || r<=lt)
return INF;
if (l>=lt && r<=rt)
return tree[x];
return min(find(2*x+1, l, (l+r)/2, lt, rt), find(2*x+2, (l+r)/2, r, lt, rt));
}
void update(int x, int l, int r, int index, int value)
{
if (l>index || r<=index)
return;
if (r-l==1)
{
tree[x]=min(tree[x], value);
return;
}
update(2*x+1, l, (l+r)/2, index, value);
update(2*x+2, (l+r)/2, r, index, value);
tree[x]=min(tree[2*x+1], tree[2*x+2]);
return;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
int l[n], r[n];
for (int i=0; i<n; i++)
cin >> l[i] >> r[i];
vector<int> temp;
for (int i=0; i<n; i++)
{
temp.push_back(l[i]);
temp.push_back(r[i]);
}
sort(temp.begin(), temp.end());
vector<int> compress;
for (auto x : temp)
if (compress.empty() || x!=compress.back())
compress.push_back(x);
for (int i=0; i<2*MAXN-1; i++)
tree[i]=INF;
for (int i=0; i<n; i++)
{
int leftindex=lower_bound(compress.begin(), compress.end(), l[i])-compress.begin();
int rightindex=lower_bound(compress.begin(), compress.end(), r[i])-compress.begin();
update(0, 0, MAXN, rightindex, leftindex);
}
int prev[compress.size()];
for (int i=0; i<compress.size(); i++)
prev[i]=-1;
for (int i=0; i<n; i++)
{
int leftindex=lower_bound(compress.begin(), compress.end(), l[i])-compress.begin();
int rightindex=lower_bound(compress.begin(), compress.end(), r[i])-compress.begin();
prev[leftindex]=find(0, 0, MAXN, leftindex, rightindex+1);
if (prev[leftindex]==leftindex)
prev[leftindex]=-1;
}
int blift[compress.size()][LOG];
for (int i=0; i<compress.size(); i++)
for (int j=0; j<LOG; j++)
blift[i][j]=-1;
for (int i=0; i<compress.size(); i++)
blift[i][0]=prev[i];
for (int j=1; j<LOG; j++)
for (int i=0; i<compress.size(); i++)
if (blift[i][j-1]!=-1)
blift[i][j]=blift[blift[i][j-1]][j-1];
/*for (int j=0; j<3; j++)
{
for (int i=0; i<compress.size(); i++)
cout << blift[i][j] << ' ';
cout << '\n';
}*/
while (q--)
{
int x, y;
cin >> x >> y;
x=x-1;
y=y-1;
if (x==y)
{
cout << 0 << '\n';
continue;
}
if (r[x]>r[y])
{
cout << "impossible" << '\n';
continue;
}
int total=1;
int i=lower_bound(compress.begin(), compress.end(), l[y])-compress.begin();
//cout << "x y " << x+1 << ' ' << y+1 << '\n';
//cout << "i " << compress[i] << '\n';
for (int j=LOG-1; j>=0; j--)
if (blift[i][j]!=-1 && compress[blift[i][j]]>r[x])
{
i=blift[i][j];
//cout << "i " << compress[i] << '\n';
total=total+(1<<j);
}
if (blift[i][0]!=-1 && compress[blift[i][0]]<=r[x])
cout << total+1 << '\n';
else
cout << "impossible" << '\n';
}
return 0;
}
Compilation message (stderr)
events.cpp: In function 'int main()':
events.cpp:64:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for (int i=0; i<compress.size(); i++)
| ~^~~~~~~~~~~~~~~~
events.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for (int i=0; i<compress.size(); i++)
| ~^~~~~~~~~~~~~~~~
events.cpp:78:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for (int i=0; i<compress.size(); i++)
| ~^~~~~~~~~~~~~~~~
events.cpp:81:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for (int i=0; i<compress.size(); i++)
| ~^~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |