Submission #1094701

#TimeUsernameProblemLanguageResultExecution timeMemory
1094701razivoEvent Hopping (BOI22_events)C++14
0 / 100
1554 ms12864 KiB
#include <iostream> #include <climits> #include <algorithm> #include <set> #include <vector> using namespace std; int main() { int N,Q; cin>>N>>Q; vector<pair<pair<int,int>,int>> ev; vector<pair<pair<int,int>,int>> u; for (int i = 0; i < N; ++i) { int x,y; cin>>x>>y; ev.emplace_back(make_pair(x,y),i); } sort(ev.begin(),ev.end(),[](pair<pair<int,int>,int> a, pair<pair<int,int>,int> b){return b.first.second>a.first.second;}); vector<int> intoev(N); for (int i = 0; i < N; ++i) { intoev[ev[i].second]=i; u.emplace_back(make_pair(ev[i].first.first,0),i); u.emplace_back(make_pair(ev[i].first.second,1),i); } sort(u.begin(),u.end()); vector<int> f(N); set<pair<int,int>> s; for (int i = 0; i < 2*N; ++i) { auto [a,j] = u[i]; if(ev[j].first.first==a.first) { s.insert({ev[j].first.second,j}); auto t = s.lower_bound({0,0}); if(t!=s.end()) { f[j]=t->second; }else f[j]=j; }else { s.erase({ev[j].first.second,j}); } } vector<pair<pair<int,int>,int>> req; for (int i = 0; i < Q; ++i) { int s,e; cin>>s>>e; s--; e--; req.emplace_back(make_pair(intoev[s],intoev[e]),i); } vector<int> ans(Q); sort(req.begin(),req.end(),[](pair<pair<int,int>,int> a, pair<pair<int,int>,int> b){return b.first.second>a.first.second;}); int cureq = 0; vector<pair<int,int>> intervals; vector<int> achiv(N); for (int i = 0; i < N; ++i) { if(f[i]==i) { intervals.emplace_back(i,i); achiv[i]=i; }else { achiv[i]=achiv[f[i]]; while(intervals.back().first>f[i]) intervals.pop_back(); if(intervals.back().first==f[i]) { intervals.back().second = i; }else { intervals.back().second = f[i]-1; intervals.emplace_back(f[i],i); } } while(req[cureq].first.second==i) { if(req[cureq].first.first==req[cureq].first.second) { ans[req[cureq].second] = 0; cureq++; continue; } if(req[cureq].first.first<achiv[i]) { ans[req[cureq].second] = -1; cureq++; continue; }else{ int min = 0; int max = intervals.size(); while(true) { int mid = (max+min)/2; if(req[cureq].first.first<intervals[mid].first) { max = mid; }else if(req[cureq].first.first>intervals[mid].second) { min = mid; }else { ans[req[cureq].second] = intervals.size()-mid; cureq++; break; } } } } } for (int i = 0; i < Q; ++i) { if(ans[i]==-1) { cout<<"impossible"<<endl; }else { cout<<ans[i]<<endl; } } }

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:29:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |         auto [a,j] = u[i];
      |              ^
#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...