Submission #1048455

#TimeUsernameProblemLanguageResultExecution timeMemory
1048455sofijavelkovskaEvent Hopping (BOI22_events)C++17
100 / 100
141 ms16208 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN=(1<<18), LOG=17; 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 (l[y]<=r[x]) cout << total+1 << '\n'; else if (blift[y][0]!=-1 && l[blift[y][0]]<=r[x]) cout << total+2 << '\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...