Submission #1094727

#TimeUsernameProblemLanguageResultExecution timeMemory
1094727razivoEvent Hopping (BOI22_events)C++14
0 / 100
230 ms10560 KiB
#include <iostream> #include <climits> #include <algorithm> #include <set> #include <vector> using namespace std; struct Seg { vector<int> t; int n; Seg(int N) { n=N; t = vector<int>(2*N,INT_MAX); } void Update(int loc, int v) { loc+=n; t[loc] = v; loc = loc/2; while(loc>0) { t[loc] = min(t[2*loc],t[2*loc+1]); loc = loc/2; } } int Query(int l,int r) { l+=n; r+=n; int res = INT_MAX; while(l!=r) { res = min(res,t[l]); if(l%2==1) { l++; } if(r%2==1) { r--; } res = min(res,t[r]); l=l/2; r=r/2; } return res; } }; 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) { if(b.first.second==a.first.second) return b.first.first>a.first.second; 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); Seg seg = Seg(N); for (int i = 0; i < N; ++i) { if(f[i]==i) { intervals.emplace_back(i,i); seg.Update(i,i); achiv[i]=i; }else{ int tem = seg.Query(f[i],i); achiv[i]=tem; seg.Update(i,tem); 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(ev[req[cureq].first.first].first.second==ev[req[cureq].first.second].first.second) { ans[req[cureq].second] = 1; cureq++; continue; } if(req[cureq].first.first<achiv[i]||req[cureq].first.first>req[cureq].first.second) { 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+1; }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:66:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |         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...