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;
typedef vector<int>vi;
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int INF=2e9;
const int MX=1e5+10;
void IO() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
/////////////////////////ONLY CLEAN CODES ALLOWED/////////////////////////
int N,Q;
vi L(MX), R(MX);
bool cmp(int i, int j){
if(R[i]!=R[j]) return R[i] < R[j];
return L[i] > L[j];
}
int main(){
IO();
cin>>N>>Q;
FOR(i,0,N) cin>>L[i]>>R[i];
vi vec(N); iota(all(vec),0);
sort(all(vec),cmp);
//for(int x: vec) cout << x << " "; cout << endl;
unordered_map<int,int>mp;
FOR(i,0,N) mp[vec[i]]=i;
vi jump(N), jump_val(N);
int mnl=INF, mnl_idx;
ROF(j,0,N){
int i=vec[j];
if(mnl<=R[i]){
jump[i]=jump[mnl_idx];
jump_val[i]=jump_val[mnl_idx]+1;
}
else{
jump[i]=i;
jump_val[i]=0;
}
if(ckmin(mnl,L[i])) mnl_idx=i;
}
//for(int x: jump_val) cout << x << " "; cout << endl;
while(Q--){
int s,e; cin>>s>>e; s--; e--;
//s=mp[s], e=mp[e];
//cout << s << " " << e << endl;
if(jump[s]==jump[e] && jump_val[s]>=jump_val[e]) cout << jump_val[s] - jump_val[e] << endl;
else cout << "impossible" << endl;
}
}
Compilation message (stderr)
events.cpp: In function 'int main()':
events.cpp:57:24: warning: 'mnl_idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
57 | jump[i]=jump[mnl_idx];
| ^
# | 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... |