Advertisement
konchin_shih

DRC#4 pA by ub33

Jun 12th, 2021
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.51 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. #define matsuri pair<int,int>
  4. using namespace std;
  5. const int iris = 1e9+7;
  6.  
  7. int tp[500010],aa[500010],bb[500010],cc[500010],dd[500010];
  8.  
  9. struct akari{
  10.     int x,y;
  11.     bool operator<(akari b)const{
  12.         return x*b.y < b.x*y;
  13.     }
  14. };
  15. akari ls[1500010];
  16. int p;
  17.  
  18. int vigna[5000010];
  19.  
  20. void mdf(int i,int l,int r,int p,int k)
  21. {
  22.     int m=(l+r)>>1;
  23.     if(l==r)
  24.     {
  25.         vigna[i]=max(vigna[i], k);
  26.         return;
  27.     }
  28.     else if(p<=m)
  29.         mdf(i*2,l,m,p,k);
  30.     else
  31.         mdf(i*2+1,m+1,r,p,k);
  32.     vigna[i]=max(vigna[i*2], vigna[i*2+1]);
  33. }
  34.  
  35. int qry(int i,int l,int r,int L,int R)
  36. {
  37.     int m=(l+r)>>1;
  38.     if(L<=l && r<=R)
  39.         return vigna[i];
  40.     else if(R<=m)
  41.         return qry(i*2,l,m,L,R);
  42.     else if(L>m)
  43.         return qry(i*2+1,m+1,r,L,R);
  44.     else
  45.         return max(qry(i*2,l,m,L,R),qry(i*2+1,m+1,r,L,R));
  46. }
  47.  
  48. int sana(int a,int b)
  49. {
  50.     akari qwq={a,b};
  51.     return lower_bound(ls,ls+p,qwq)-ls;
  52. }
  53.  
  54. signed main()
  55. {
  56.     ios::sync_with_stdio(0);
  57.     cin.tie(0);
  58.    
  59.     int n,i,a,b,ans;
  60.     cin>>n;
  61.     for(i=0;i<n;i++)
  62.     {
  63.         cin>>tp[i];
  64.         if(!tp[i])
  65.         {
  66.             cin>>aa[i]>>bb[i];
  67.             ls[p++]={aa[i], bb[i]};
  68.         }
  69.         else
  70.         {
  71.             cin>>aa[i]>>bb[i]>>cc[i]>>dd[i];
  72.             ls[p++]={aa[i], bb[i]};
  73.             ls[p++]={cc[i], dd[i]};
  74.         }
  75.     }
  76.     sort(ls,ls+p);
  77.     for(i=0;i<n;i++)
  78.     {
  79.         if(!tp[i])
  80.         {
  81.             a=aa[i];
  82.             b=bb[i];
  83.             mdf(1,0,p,sana(a,b),a);
  84.         }
  85.         else
  86.         {
  87.             a=sana(aa[i], bb[i]);
  88.             b=sana(cc[i], dd[i]);
  89.             if(a>b)
  90.                 swap(a,b);
  91.             ans=qry(1,0,p,a,b);
  92.             if(ans==0)
  93.                 ans=-1;
  94.             cout<<ans<<'\n';
  95.         }
  96.     }
  97.    
  98.     return 0;
  99. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement