Advertisement
pypcdev

Untitled

Jun 12th, 2021
573
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.11 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #include<ext/pb_ds/assoc_container.hpp>
  3. #include<ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6. typedef long long ll;
  7. typedef unsigned long long ull;
  8. typedef long double ld;
  9. #define int ll
  10. #define fi first
  11. #define se second
  12. #define pb push_back
  13. #define pf push_front
  14. #define ppb pop_back
  15. #define ppf pop_front
  16. #define mkp make_pair
  17. #define INF (ll)1e18
  18. #define INF2 (ll)2e18
  19. #define INF3 (ll)3e18
  20. #define INF4 (ll)4e18
  21. #define inf (signed)1e9
  22. #define inf2 (signed)2e9
  23. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  24. #define rand rng
  25. template<typename type,typename comp>
  26. 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
  27. // aset<int,less<int>> is set, but aset<int,less_equal<int> is multiset
  28. const pair<int,int>DIR4[4]={{1,0},{-1,0},{0,1},{0,-1}}; // dirs for 4 ways(like in a matrix)
  29.  
  30. // debug tools only
  31. template<typename F,typename S>
  32. ostream&operator<<(ostream&output,const pair<F,S>&data)
  33. {
  34.     output<<"{"<<data.fi<<","<<data.se<<"}";
  35.     return output;
  36. }
  37. template<typename T>
  38. ostream&operator<<(ostream&output,const set<T>&data){
  39.     if(data.empty())output<<"{}";
  40.     else{
  41.         output<<"{"<<*data.begin();
  42.         for(auto it=next(data.begin());it!=data.end();it++)cout<<","<<*it;
  43.         output<<"}";
  44.     }
  45.     return output;
  46. }
  47. template<typename T>
  48. ostream&operator<<(ostream&output,const aset<T,less<T>>&data){
  49.     if(data.empty())output<<"{}";
  50.     else{
  51.         output<<"{"<<*data.begin();
  52.         for(auto it=next(data.begin());it!=data.end();it++)cout<<","<<*it;
  53.         output<<"}";
  54.     }
  55.     return output;
  56. }
  57. template<typename T>
  58. ostream&operator<<(ostream&output,const aset<T,greater<T>>&data){
  59.     if(data.empty())output<<"{}";
  60.     else{
  61.         output<<"{"<<*data.begin();
  62.         for(auto it=next(data.begin());it!=data.end();it++)cout<<","<<*it;
  63.         output<<"}";
  64.     }
  65.     return output;
  66. }
  67. template<typename T>
  68. ostream&operator<<(ostream&output,const multiset<T>&data){
  69.     if(data.empty())output<<"{}";
  70.     else{
  71.         output<<"{"<<*data.begin();
  72.         for(auto it=next(data.begin());it!=data.end();it++)cout<<","<<*it;
  73.         output<<"}";
  74.     }
  75.     return output;
  76. }
  77. template<typename T>
  78. ostream&operator<<(ostream&output,const vector<T>&data){
  79.     if(data.empty())output<<"{}";
  80.     else{
  81.         output<<"{"<<*data.begin();
  82.         for(auto it=next(data.begin());it!=data.end();it++)cout<<","<<*it;
  83.         output<<"}";
  84.     }
  85.     return output;
  86. }
  87.  
  88.  
  89.  
  90.  
  91.  
  92.  
  93.  
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
  103.  
  104.  
  105.  
  106.  
  107.  
  108.  
  109.  
  110.  
  111.  
  112.  
  113.  
  114.  
  115.  
  116.  
  117.  
  118.  
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128.  
  129.  
  130.  
  131.  
  132.  
  133.  
  134. struct event{
  135.     int type;int time;int index;
  136. };
  137. vector<event>events;
  138. vector<pair<pair<int,int>,int>>segs;
  139. signed main(){
  140.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  141.     int n;
  142.     cin>>n;
  143.     for(int i=0;i<n;i++){
  144.         int S,E;
  145.         cin>>S>>E;
  146.         if(S>E)swap(S,E);
  147.         events.pb({1,E,i}); //end, first
  148.         events.pb({2,S,i}); //start, second
  149.         segs.pb({{S,E},i});
  150.     }
  151.     sort(events.begin(),events.end(),[](event l,event r){
  152.         return l.time<r.time||(l.time==r.time&&l.type<r.type);
  153.     });
  154.     int ans=INF;int last_i=INF;
  155.     int ans1=-1,ans2=-1;
  156.     int cnt=0;int last=0;
  157.     for(auto [type,time,index]:events){
  158.         if(type==1){
  159.             if(cnt>=2){
  160.                 int new_ans=time-last;
  161.                 if(new_ans<ans){
  162.                     ans=new_ans;
  163.                     ans1=last_i;
  164.                     ans2=index;
  165.                 }
  166.             }
  167.         }
  168.         if(type==1)cnt--;
  169.         if(type==2)cnt++;
  170.         if(type==2)last=time,last_i=index;
  171.     }
  172.  
  173.     if(ans==INF){
  174.         cout<<"0\n";
  175.         return 0;
  176.     }
  177.     if(ans1!=ans2){
  178.         cout<<ans1+1<<" "<<ans2+1<<"\n";
  179.         return 0;
  180.     }
  181.     for(auto seg:segs){
  182.         if(seg.se!=ans1){
  183.             if(seg.fi.fi<=segs[ans1].fi.fi&&seg.fi.se>=segs[ans1].fi.se){
  184.                 cout<<ans1+1<<" "<<seg.se+1<<"\n";
  185.                 return 0;
  186.             }
  187.         }
  188.     }
  189.     cout<<0/0<<"=0/0\n";
  190. }
  191.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement