Advertisement
Guest User

Untitled

a guest
Apr 8th, 2020
174
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.01 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long best[100010],n,xw,yw,xh,yh,r,prox[100010];
  5. pair<long long, long long> pl[100010];
  6. vector<long long> a;
  7.  
  8. int main(){
  9.     scanf("%lld", &n);
  10.     scanf("%lld %lld %lld %lld", &xh , &yh, &xw, &yw);
  11.     for(int i=0;i<n;i++) scanf("%lld %lld", &pl[i].first, &pl[i].second);
  12.     sort(pl,pl+n);
  13.     for(long long i=0;i<n;i++){
  14.         if((pl[i].first<xh && pl[i].first<xw) || (pl[i].first>xh && pl[i].first>xw) || (pl[i].second<yh && pl[i].second<yw) || (pl[i].second>yh && pl[i].second>yw)) continue;
  15.         a.push_back(pl[i].second);
  16.         if((xh>xw && yh<yw) || (xh<xw && yh>yw)) a.back()*=-1;
  17.     }
  18.     if(a.size()==0){
  19.         printf("0\n");
  20.         return 0;
  21.     }
  22.     r=1;
  23.     best[a.size()-1]=1;
  24.     prox[a.size()-1]=0;
  25.     for(long long i=a.size()-2;i>=0;i--){
  26.         long long j=i+1;
  27.         while(true){
  28.             if(!j){
  29.                 best[i]=1;
  30.                 prox[i]=0;
  31.                 break;
  32.             }
  33.             if(a[i]<=a[j]){
  34.                 best[i]=1+best[j];
  35.                 prox[i]=j;
  36.                 break;
  37.             }
  38.             j=prox[j];
  39.         }
  40.         r=max(r,best[i]);
  41.     }
  42.     printf("%lld\n", r);
  43.     return 0;
  44. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement