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), INF=1e9;
int n;
int l[MAXN], r[MAXN];
int tree[2*MAXN-1];
bool rcompare(int x, int y)
{
if (r[x]==r[y])
return l[x]<l[y];
return r[x]<r[y];
}
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 q;
cin >> n >> q;
for (int i=0; i<n; i++)
cin >> l[i] >> r[i];
int sorted[n];
for (int i=0; i<n; i++)
sorted[i]=i;
sort(sorted, sorted+n, rcompare);
int ranked[n];
for (int i=0; i<n; i++)
ranked[sorted[i]]=i;
map<int, int> compress;
for (int i=0; i<n; i++)
{
compress[l[i]]=0;
compress[r[i]]=0;
}
int counter=0;
for (auto x : compress)
{
compress[x.first]=counter;
counter=counter+1;
}
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;
}
if (r[x]==r[y])
{
cout << 1 << '\n';
continue;
}
for (int i=0; i<2*MAXN-1; i++)
tree[i]=INF;
int dp[n];
dp[ranked[y]]=0;
update(0, 0, MAXN, compress[l[y]], 0);
for (int i=ranked[y]-1; i>=0; i--)
{
dp[i]=min(INF, find(0, 0, MAXN, 0, compress[r[sorted[i]]]+1)+1);
//cout << "l r " << l[sorted[i]] << ' ' << r[sorted[i]] << '\n';
//cout << "find " << find(0, 0, MAXN, 0, compress[r[sorted[i]]]+1) << '\n';
update(0, 0, MAXN, compress[l[sorted[i]]], dp[i]);
//cout << "dp " << dp[i] << '\n';
}
if (dp[ranked[x]]!=INF)
cout << dp[ranked[x]] << '\n';
else
cout << "impossible" << '\n';
}
return 0;
}
/*#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5, LOG=17;
int n;
int l[MAXN], r[MAXN];
bool rcompare(int x, int y)
{
if (r[x]<r[y])
return true;
return false;
}
bool lcompare(int x, int y)
{
if (l[x]<l[y])
return true;
return false;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int q;
cin >> n >> q;
for (int i=0; i<n; i++)
cin >> l[i] >> r[i];
int sorted[n];
for (int i=0; i<n; i++)
sorted[i]=i;
sort(sorted, sorted+n, rcompare);
int ranked[n];
for (int i=0; i<n; i++)
ranked[sorted[i]]=i;
int lsorted[n];
for (int i=0; i<n; i++)
lsorted[i]=i;
sort(lsorted, lsorted+n, lcompare);
int t=n-1;
set<int> farthest;
for (int i=0; i<n; i++)
farthest.insert(i);
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=n-1; i>=0; i--)
{
while (t>=0 && l[lsorted[t]]>r[sorted[i]])
{
farthest.erase(ranked[lsorted[t]]);
t=t-1;
}
auto it=farthest.end();
it--;
if (*it!=i)
blift[i][0]=*it;
}
for (int j=1; j<LOG; j++)
for (int i=0; i<n; i++)
if (blift[i][j-1]!=-1 && blift[blift[i][j-1]][j-1]!=-1)
blift[i][j]=blift[blift[i][j-1]][j-1];
while (q--)
{
int x, y;
cin >> x >> y;
x=ranked[x-1];
y=ranked[y-1];
if (x>y)
{
cout << "impossible" << '\n';
continue;
}
if (x==y)
{
cout << 0 << '\n';
continue;
}
int total=0;
for (int j=LOG-1; j>=0; j--)
{
if (blift[x][j]!=-1 && blift[x][j]<y)
{
x=blift[x][j];
total=total+(1<<j);
}
}
if (blift[x][0]>=y)
cout << total+1 << '\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... |