Submission #1047295

#TimeUsernameProblemLanguageResultExecution timeMemory
1047295sofijavelkovskaEvent Hopping (BOI22_events)C++17
20 / 100
247 ms17552 KiB
#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]; /*cout << "blift\n"; for (int j=0; j<LOG; j++) { for (int i=0; i<n; i++) cout << blift[i][j] << ' '; cout << '\n'; }*/ /*for (int i=0; i<n; i++) cout << ranked[i] << ' '; cout << '\n'; for (int i=0; i<n; i++) cout << blift[i][0] << ' '; cout << '\n';*/ 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--) { //cout << "x " << x << '\n'; 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 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...