Submission #1047419

#TimeUsernameProblemLanguageResultExecution timeMemory
1047419sofijavelkovskaEvent Hopping (BOI22_events)C++17
10 / 100
1600 ms9044 KiB
#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 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...