abdelrahman_orief

Untitled

Sep 20th, 2020
867
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3. #define mod 1000000007
  4. #define int long long
  5. #pragma GCC optimize("-Ofast")
  6. #define float double
  7. #define PI 3.141592653589793238462643383279502884
  8. #define sinDegrees(x) sin((x) * PI / 180.0)
  9. #define tanDegrees(x) tan((x) * PI / 180.0)
  10. #define atanDegrees(x) atan(x)* 180.0 / PI
  11.  
  12. using namespace std;
  13.  
  14. int tree[600000];
  15. int p;
  16.  
  17. void update(int k, int x)
  18. {
  19.     k+=p;
  20.     tree[k] = x;
  21.  
  22.     for (k/=2;k>=1;k/=2)
  23.     {
  24.         tree[k] = max(tree[2*k], tree[2*k+1]);
  25.     }
  26. }
  27.  
  28. int get(int a, int b)
  29. {
  30.     int sol=0;
  31.     a+=p; b+=p;
  32.  
  33.     while (a<=b)
  34.     {
  35.         if (a%2==1)
  36.         {
  37.             sol = max(sol, tree[a]);
  38.             a++;
  39.         }
  40.         if (b%2==0)
  41.         {
  42.             sol = max(sol, tree[b]);
  43.             b--;
  44.         }
  45.         a/=2;b/=2;
  46.     }
  47.     return sol;
  48. }
  49.  
  50. int32_t main()
  51. {
  52.     ios_base::sync_with_stdio(false);
  53.     cin.tie(0);
  54.  
  55.     int t, st;
  56.     cin>>t>>st;
  57.  
  58.     while (t--)
  59.     {
  60.         memset(tree, 0, sizeof(tree));
  61.         int n, q;
  62.         cin>>n>>q;
  63.         for (int i=0;i<n+5;i++)
  64.         {
  65.             p = 1<<i;
  66.             if (p>=n)
  67.             {
  68.                 break;
  69.             }
  70.         }
  71.         int arr[n], last;
  72.         vector<int> overflow;
  73.  
  74.         for (int i=0;i<n;i++)
  75.         {
  76.             int a;
  77.             cin>>a;
  78.             if (i==0)
  79.             {
  80.                 arr[i]=1;
  81.                 last = a;
  82.             }
  83.             else
  84.             {
  85.                 if (a>=last)
  86.                     arr[i]=arr[i-1]+1;
  87.                 else
  88.                 {
  89.                     arr[i] = 1;
  90.                     overflow.push_back(arr[i-1]);
  91.                 }
  92.  
  93.             }
  94.             last = a;
  95.             update(i, arr[i]);
  96.         }
  97.         overflow.push_back(arr[n-1]);
  98.  
  99.         int left[n], overIndex=0;
  100.         for (int i=0;i<n;i++)
  101.         {
  102.             left[i] = overflow[overIndex] - arr[i] +1;
  103.             if (left[i]==1)
  104.                 overIndex++;
  105.         }
  106.  
  107.         while (q--)
  108.         {
  109.             int a, b;
  110.             cin>>a>>b;
  111.             a--;b--;
  112.             int l = a+left[a], r=b;
  113.  
  114.             cout<<max(get(l, r), arr[a+left[a]-1]-arr[a]+1)<<endl;
  115.         }
  116.  
  117.  
  118.     }
  119.  
  120.  
  121. }
  122. /*
  123. 1 1
  124. 9 2
  125. 3 2 1 3 2 1 3 2 1
  126. 5 6
  127. 1 6
  128. */
  129.  
RAW Paste Data