#include <bits/stdc++.h>
/*
The whole event space is a DAG
Calculate the minimum switching to get from time A to B
Get from an event to another
Event to event
Every event is either completely contained in another, or not
Completely contained = directed edge from contained
Not = earlier end to later end
An O(E) = O(N^2) should get 35 points
Use RQTree to get minimum switches by sorting by end time; O(NQ log N)
You cannot switch to an event with same end time; waste
ST5: Earlier start time = earlier end time (start time is increasing)
Go backwards and use segment tree
ST4: O(NQ), not O(NQ log N)
Go backwards; min switches from is increasing
You now have to go from a time to an event
Switches can be calculated by using min number of switches for every time
If the start (end) event was not a key event, add 1
Edges split and join; an event inside another is just a join
Select a chain of events with minimum switches
If there was a chain that connected two events, it would have to be part of the main chain
1 2 3 4 5 6 7
\ /
S 1 2 3E
1 2 3 4 5 6
Update a chain?
If the start is moved forward, the chain stays
If the end is moved backward, the chain ?
If start is moved backwards, extend the chain
*/
int n,q;
std::vector<int> rqtree;
std::vector<int> endpoints;
int query(int l,int r,int nl=0,int nr=n+1,int ni=0){
//std::cout<<nl<<"/"<<nr<<'\n';
if(nl+1>=nr){
if(l<=endpoints[nl]&&r>endpoints[nl])return rqtree[ni];
return 1000000001;
}
if(l>=endpoints[nr]||r<=endpoints[nl])return 1000000001;
if(l<=endpoints[nl]&&r>=endpoints[nr]){
return rqtree[ni];
}
int nm=(nl+nr)/2;
return std::min(query(l,r,nl,nm,ni+1),query(l,r,nm,nr,ni+2*(nm-nl)));
}
void update(int loc,int val,int nl=0,int nr=n+1,int ni=0){
//std::cout<<"upd "<<nl<<' '<<nr<<'\n';
if(nl+1>=nr){
if(loc==endpoints[nl])rqtree[ni]=std::min(rqtree[ni],val);
return;
}
int nm=(nl+nr)/2;
if(loc<endpoints[nm]){
rqtree[ni]=std::min(rqtree[ni],val);
update(loc,val,nl,nm,ni+1);
}else{
rqtree[ni]=std::min(rqtree[ni],val);
update(loc,val,nm,nr,ni+2*(nm-nl));
}
}
std::vector<std::pair<int,int>> events;
std::vector<std::pair<int,int>> queries;
std::vector<int> s_events;
std::vector<int> i_s_events;
std::vector<int> out_arr;
int main(){
std::cin>>n>>q;
for(int i=0;i<n;i++){
int a,b;
std::cin>>a>>b;
events.push_back({a,b});
endpoints.push_back(b);
s_events.push_back(i);
}
endpoints.push_back(0);
endpoints.push_back(1000000001);
std::sort(endpoints.begin(),endpoints.end());
std::sort(s_events.begin(),s_events.end(),[](int a,int b){return events[a].second==events[b].second?events[a].first<events[b].first:events[a].second<events[b].second;});
i_s_events.resize(n,-1);
for(int i=0;i<n;i++){
i_s_events[s_events[i]]=i;
}
for(int i=0;i<q;i++){
int start,end;
std::cin>>start>>end;
start--,end--;
int cswc=0;//count
int cset=1000000001;//end time
int nset=1000000001;//next end time (first start)
cset=nset=events[end].first;
int f_index=std::upper_bound(endpoints.begin(),endpoints.end(),events[end].second)-endpoints.begin()-2;
int s_index=i_s_events[start];
//std::cout<<s_index<<" to "<<f_index<<'\n';
//std::cout<<events[end].second<<"?\n";
if(events[start].second<events[end].second){
cswc=-1;
}
if(start==end){
std::cout<<"0\n";
continue;
}
for(int p=f_index;p>=s_index;p--){
//if(p==i_s_events[end])continue;
int ceid=s_events[p];
//std::cout<<ceid<<";\n";
if(events[ceid].second<nset){
cswc=-1;
break;
}else if(events[ceid].second<cset){
//std::cout<<"inc\n";
cswc++;
cset=nset;
}else{
}
nset=std::min(nset,events[ceid].first);
}
if(cswc==-1){
std::cout<<"impossible\n";
}else{
std::cout<<cswc+1<<'\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1580 ms |
2904 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
