Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #include<ext/pb_ds/assoc_container.hpp>
- #include<ext/pb_ds/tree_policy.hpp>
- using namespace std;
- using namespace __gnu_pbds;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- #define int ll
- #define fi first
- #define se second
- #define pb push_back
- #define pf push_front
- #define ppb pop_back
- #define ppf pop_front
- #define mkp make_pair
- #define INF (ll)1e18
- #define INF2 (ll)2e18
- #define INF3 (ll)3e18
- #define INF4 (ll)4e18
- #define inf (signed)1e9
- #define inf2 (signed)2e9
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- #define rand rng
- template<typename type,typename comp>
- using aset=tree<type,null_type,comp,rb_tree_tag,tree_order_statistics_node_update>;// advanced set with order_of_key and find_by_order
- // aset<int,less<int>> is set, but aset<int,less_equal<int> is multiset
- const pair<int,int>DIR4[4]={{1,0},{-1,0},{0,1},{0,-1}}; // dirs for 4 ways(like in a matrix)
- // debug tools only
- template<typename F,typename S>
- ostream&operator<<(ostream&output,const pair<F,S>&data)
- {
- output<<"{"<<data.fi<<","<<data.se<<"}";
- return output;
- }
- template<typename T>
- ostream&operator<<(ostream&output,const set<T>&data){
- if(data.empty())output<<"{}";
- else{
- output<<"{"<<*data.begin();
- for(auto it=next(data.begin());it!=data.end();it++)cout<<","<<*it;
- output<<"}";
- }
- return output;
- }
- template<typename T>
- ostream&operator<<(ostream&output,const aset<T,less<T>>&data){
- if(data.empty())output<<"{}";
- else{
- output<<"{"<<*data.begin();
- for(auto it=next(data.begin());it!=data.end();it++)cout<<","<<*it;
- output<<"}";
- }
- return output;
- }
- template<typename T>
- ostream&operator<<(ostream&output,const aset<T,greater<T>>&data){
- if(data.empty())output<<"{}";
- else{
- output<<"{"<<*data.begin();
- for(auto it=next(data.begin());it!=data.end();it++)cout<<","<<*it;
- output<<"}";
- }
- return output;
- }
- template<typename T>
- ostream&operator<<(ostream&output,const multiset<T>&data){
- if(data.empty())output<<"{}";
- else{
- output<<"{"<<*data.begin();
- for(auto it=next(data.begin());it!=data.end();it++)cout<<","<<*it;
- output<<"}";
- }
- return output;
- }
- template<typename T>
- ostream&operator<<(ostream&output,const vector<T>&data){
- if(data.empty())output<<"{}";
- else{
- output<<"{"<<*data.begin();
- for(auto it=next(data.begin());it!=data.end();it++)cout<<","<<*it;
- output<<"}";
- }
- return output;
- }
- struct event{
- int type;int time;int index;
- };
- vector<event>events;
- vector<pair<pair<int,int>,int>>segs;
- signed main(){
- ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
- int n;
- cin>>n;
- for(int i=0;i<n;i++){
- int S,E;
- cin>>S>>E;
- if(S>E)swap(S,E);
- events.pb({1,E,i}); //end, first
- events.pb({2,S,i}); //start, second
- segs.pb({{S,E},i});
- }
- sort(events.begin(),events.end(),[](event l,event r){
- return l.time<r.time||(l.time==r.time&&l.type<r.type);
- });
- int ans=INF;int last_i=INF;
- int ans1=-1,ans2=-1;
- int cnt=0;int last=0;
- for(auto [type,time,index]:events){
- if(type==1){
- if(cnt>=2){
- int new_ans=time-last;
- if(new_ans<ans){
- ans=new_ans;
- ans1=last_i;
- ans2=index;
- }
- }
- }
- if(type==1)cnt--;
- if(type==2)cnt++;
- if(type==2)last=time,last_i=index;
- }
- if(ans==INF){
- cout<<"0\n";
- return 0;
- }
- if(ans1!=ans2){
- cout<<ans1+1<<" "<<ans2+1<<"\n";
- return 0;
- }
- for(auto seg:segs){
- if(seg.se!=ans1){
- if(seg.fi.fi<=segs[ans1].fi.fi&&seg.fi.se>=segs[ans1].fi.se){
- cout<<ans1+1<<" "<<seg.se+1<<"\n";
- return 0;
- }
- }
- }
- cout<<0/0<<"=0/0\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement