Submission #1047461

#TimeUsernameProblemLanguageResultExecution timeMemory
1047461sofijavelkovskaEvent Hopping (BOI22_events)C++17
0 / 100
168 ms5200 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN=1e5; int n; int l[MAXN], r[MAXN]; bool rcompare(int x, int y) { if (r[x]==r[y]) return l[x]<l[y]; return r[x]<r[y]; } int main() { 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 group[n]; int current=0; int ranked[n]; for (int i=0; i<n; i++) { ranked[sorted[i]]=i; if (i==0 || l[sorted[i]]<=r[sorted[i-1]]) group[sorted[i]]=current; else { current=current+1; group[sorted[i]]=current; } } while (q--) { int x, y; cin >> x >> y; x=x-1; y=y-1; if (group[x]!=group[y]) { cout << "impossible" << '\n'; continue; } if (x==y) { cout << 0 << '\n'; continue; } if (r[x]==r[y]) { cout << 1 << '\n'; continue; } cout << ranked[y]-ranked[x] << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...