Submission #750727

#TimeUsernameProblemLanguageResultExecution timeMemory
750727Melika0ghEvent Hopping (BOI22_events)C++17
0 / 100
1085 ms524288 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define sync ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define pii pair<int, int> #define pb push_back #define mp make_pair #define fi first #define se second //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxn = 1e5 + 10, inf = 1e9 + 7, mood = 1e9+7, mood2 = 19025953, base = 31, maxsq = 400, maxlg = 20; vector<pii> query[maxn]; int s[maxn], f[maxn], ans[maxn]; vector<int> order; int n, q; bool cmp(int a, int b) { return mp(s[a], f[a]) < mp(s[b], f[b]); } bool cmp2(int a, int b) { return mp(f[a], s[a]) < mp(f[b], s[b]); } int main() { sync; cin >> n >> q; for(int i = 1; i <= n; i++) cin >> s[i] >> f[i], order.pb(i); for(int i = 0; i < q; i++) { int ss, ff; cin >> ss >> ff; query[ss].pb(mp(ff, i)); ans[i] = 0 - maxn; } sort(order.begin(), order.end(), cmp); for(int i = 0; i < n; i++) { int v = order[i]; vector<int> vc, vc2; int j = i+1; int u; if(j < n) { u = order[j]; while(s[u] <= f[v] && j < n) { vc.pb(f[u]); vc2.pb(u); j++; if(j >= n) break; u = order[j]; } } if(!vc.empty()) { sort(vc.begin(), vc.end()); sort(vc2.begin(), vc2.end(), cmp2); } for(auto x : query[v]) { // cout << v << endl; u = x.fi; int ind = x.se; if(u == v) { ans[ind] += maxn; continue; } if(vc.empty()) continue; if(vc.back() <= f[u]) { ans[ind]++; int tmpp = lower_bound(vc.begin(), vc.end(), vc.back()) - vc.begin(); query[vc2[tmpp]].pb(x); continue; } int tmp = lower_bound(vc.begin(), vc.end(), f[u]) - vc.begin(); while(vc[tmp] > f[u] && tmp > 0) tmp--; if(vc[tmp] > f[u]) continue; ans[ind]++; query[vc2[tmp]].pb(x); } query[v].clear(); } for(int i = 0; i < q; i++) { if(ans[i] < 0) cout << "impossible" << '\n'; else cout << ans[i] << '\n'; } }
#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...