Submission #1047440

#TimeUsernameProblemLanguageResultExecution timeMemory
1047440sofijavelkovskaEvent Hopping (BOI22_events)C++17
25 / 100
1268 ms100616 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN=5e3, INF=1e9; 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]; } 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; 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; } int lsorted[n]; for (int i=0; i<n; i++) lsorted[i]=i; sort(lsorted, lsorted+n, lcompare); int answer[n][n]; for (int i=0; i<n; i++) for (int j=0; j<n; j++) { if (i==j) answer[i][j]=0; else if (r[i]==r[j]) answer[i][j]=1; else answer[i][j]=-1; } for (int y=0; y<n; y++) { int dp[n]; dp[ranked[y]]=0; multiset<int> best; best.insert(0); //update(0, 0, MAXN, compress[l[y]], 0); int t=n-1; for (int i=ranked[y]-1; i>=0; i--) { while (t>=0 && l[lsorted[t]]>r[sorted[i]]) { if (ranked[lsorted[t]]<=ranked[y] && dp[ranked[lsorted[t]]]!=INF) best.erase(best.find(dp[ranked[lsorted[t]]])); t=t-1; } dp[i]=INF; if (!best.empty()) dp[i]=*best.begin()+1; if (dp[i]!=INF) best.insert(dp[i]); if (dp[i]!=INF) answer[sorted[i]][y]=dp[i]; //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'; } } //for (int i=0; i<n; i++) // for (int j=0; j<n; j++) // cout << i+1 << ' ' << j+1 << ' ' << answer[i][j] << '\n'; while (q--) { int x, y; cin >> x >> y; x=x-1; y=y-1; if (answer[x][y]!=-1) cout << answer[x][y] << '\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...