Ganesh1648

SEAD problem

Jun 3rd, 2020
44
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define pb push_back
  6. #define vi vector<int>
  7. #define vpii vector<pair<int,int>>
  8. //#define N 2e5+5
  9. #define f first
  10. #define s second
  11. #define all(x) x.begin(),x.end()
  12. #define int long long int
  13. #define forn(i,n) for(int i=0;i<n;i++)
  14. #define fore(i,l,r) for(int i=l;i<r;i++)
  15. #define sz(a) (int)((a).size())
  16. #define ll long long
  17. #define ar array
  18. #define init(arr) memset(arr,0,sizeof(arr))
  19.  
  20. int n,m,t,d,L,R,n1;
  21. const int N=1e5+5;
  22. const int M=16;
  23. int sp[M][N];
  24. int binarySearch(int arr[])
  25. {
  26.     int ans=0;
  27.     int l=0,r=n-1;
  28.     while(l<=r)
  29.     {
  30.         int mid=l+(r-l)/2;
  31.         if(arr[mid]<=t)
  32.         {
  33.             ans=mid;
  34.             l=mid+1;
  35.         }
  36.         else
  37.             r=mid-1;
  38.     }
  39.     return ans;
  40. }
  41. void consSparse(int b[])
  42. {
  43.     int p=log2(n1);
  44.     for(int i=1;i<=p;i++)
  45.     {
  46.         for(int j=0;(j+(1<<i)-1)<n1;j++)
  47.         {
  48.             if(b[sp[i-1][j]]>b[sp[i-1][j+(1<<(i-1))]])
  49.                 sp[i][j]=sp[i-1][j];
  50.             else
  51.                 sp[i][j]=sp[i-1][j+(1<<(i-1))];
  52.         }
  53.     }
  54. }
  55. bool RMQ(int x,int b[])
  56. {
  57.    
  58.     int l=R-x;
  59.     int ans;
  60.     int p=log2(l);
  61.     // cout<<b[sp[p][x]]<<" "<<b[sp[p][R-(1<<p)]]<<"\n";
  62.     if(b[sp[p][x]]>b[sp[p][R-(1<<p)]])
  63.         ans=(b[sp[p][x]]);
  64.    
  65.     else
  66.         ans=(b[sp[p][R-(1<<p)]]);
  67.    
  68.     // cout<<ans<<" "<<d<<"\n";
  69.     if(ans<=d)
  70.         return true;
  71.  
  72.     return false;        
  73. }
  74. void solve()
  75. {
  76.     init(sp);
  77.     cin>>n;
  78.     n1=n-1;
  79.     int a[n],b[n1];
  80.     forn(i,n)
  81.         cin>>a[i];
  82.     forn(i,n-1)
  83.         b[i]=a[i+1]-a[i];
  84.     cin>>m;
  85.     forn(i,n-1)
  86.         sp[0][i]=i;
  87.     consSparse(b);
  88.    
  89.     while(m-->0)
  90.     {
  91.         cin>>t>>d;
  92.         R=binarySearch(a);
  93.         int r=R-1;
  94.         L=0;
  95.         int l=0;
  96.         int ans=R;
  97.         while(l<=r)
  98.         {
  99.             int mid=l+(r-l)/2;
  100.             if(RMQ(mid,b))
  101.             {
  102.                 ans=mid;
  103.                 r=mid-1;
  104.             }
  105.             else
  106.                 l=mid+1;
  107.         }
  108.    
  109.             cout<<ans+1<<"\n";
  110.     }
  111. }
  112. int32_t main() {
  113.     ios_base::sync_with_stdio(false);
  114.     cin.tie(NULL);
  115.     solve();
  116. }
RAW Paste Data