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 l[MAXN], r[MAXN];
int tree[2*MAXN-1];
int compare(int x, int y)
{
if (x==-1 || y==-1)
return max(x, y);
if (l[x]<l[y])
return x;
return y;
}
int find(int x, int l, int r, int lt, int rt)
{
if (l>=rt || r<=lt)
return -1;
if (l>=lt && r<=rt)
return tree[x];
return compare(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]=compare(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]=compare(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;
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]=-1;
for (int i=0; i<n; i++)
{
int rightindex=lower_bound(compress.begin(), compress.end(), r[i])-compress.begin();
update(0, 0, MAXN, rightindex, i);
}
int prev[n];
for (int i=0; i<n; 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[i]=find(0, 0, MAXN, leftindex, rightindex+1);
if (prev[i]==i)
prev[i]=-1;
}
int blift[n][LOG];
for (int i=0; i<n; i++)
for (int j=0; j<LOG; j++)
blift[i][j]=-1;
for (int i=0; i<n; i++)
blift[i][0]=prev[i];
for (int j=1; j<LOG; j++)
for (int i=0; i<n; 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<n; i++)
cout << blift[i][j]+1 << ' ';
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=0;
//int i=lower_bound(compress.begin(), compress.end(), l[y])-compress.begin();
//cout << "x y " << x+1 << ' ' << y+1 << '\n';
//cout << "y " << y+1 << '\n';
for (int j=LOG-1; j>=0; j--)
if (blift[y][j]!=-1 && l[blift[y][j]]>r[x])
{
y=blift[y][j];
//cout << "y " << y+1 << '\n';
total=total+(1<<j);
}
if (blift[y][0]!=-1 && l[blift[y][0]]<=r[x])
cout << total+2 << '\n';
else
cout << "impossible" << '\n';
}
return 0;
}
# | 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... |