Advertisement
_no0B

Untitled

Jan 23rd, 2022
797
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #define LL long long
  3. #define N ((int)1e5 + 8)
  4. #define MAX ((int)1e9 + 8)
  5. #define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
  6. #define Type pair < int , int >
  7.  
  8. using namespace std;
  9.  
  10. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // generator
  11.  
  12.  
  13. int GetRandomNumber(int a , int b)
  14. {
  15.     return uniform_int_distribution<int>(a, b)(rng); //rand([a,b])
  16. }
  17.  
  18.  
  19. Type Opp(Type a , Type b, int type)
  20. {
  21.     if(type == 0) return min(a,b);
  22.     if(type == 1) return max(a,b);
  23. }
  24.  
  25. int range[N];
  26.  
  27. void PreProcess(int n , vector < vector < Type > >& tab , vector < int >& arr, int type)
  28. {
  29.     for(int i = 1 ; i <= n ; i++) tab[i][0] = {arr[i] , i};
  30.     for(int p = 1 ; p <= 20 ; p++){
  31.         for(int i = 1 ; i <= n ; i++){
  32.             tab[i][p] = tab[i][p-1];
  33.             ///int L = (i + 2^p - 1) - 2^(p-1) + 1; => i + 2^p - 2^(p-1) => i + 2^(p-1)
  34.             int L = i + (1<<(p-1));
  35.             if(L <= n) tab[i][p] = Opp(tab[i][p] , tab[L][p-1], type);
  36.         }
  37.     }
  38.     /// O(nlogn)
  39.  
  40.  
  41. }
  42.  
  43. void Cal(int n)
  44. {
  45.     range[1] = 0; /// range[len] = p ; 2^p <= len and 2^(p+1) > len
  46.     for(int i = 2 ; i <= n ; i++){
  47.         range[i] = range[i-1];
  48.         if((i & (i-1)) == 0) range[i]++;
  49.         ///range[i] = range[i/2] + 1;
  50.     }
  51. }
  52.  
  53.  
  54.  
  55. Type Query(int L , int R , vector < vector < int > >& tab, int type) /// find minimum, overlapping allowed
  56. {
  57.     if(L > R) return MAX; /// invalid
  58.     int len = R - L + 1;
  59.     int p = range[len];
  60.     ///int i = L + (1<<p) - 1;
  61.     int ans = tab[L][p]; /// green portion
  62.     int i = R - (1<<p) + 1;
  63.     ans = Opp(ans , tab[i][p], type); /// blue portion
  64.     return ans;
  65. } /// O(1)
  66.  
  67.  
  68. int main()
  69. {
  70.     /// problem: https://lightoj.com/problem/ghajini
  71.     int n , d;
  72.     cin>>n>>d;
  73.     vector < int > arr(n+1);
  74.     for(int i = 1 ; i <= n ; i++) cin>>arr[i];
  75.     vector < vector < int > > maxTab(n+1 , vector < int >(22)) , minTab(n+1 , vector < int >(22));
  76.     Cal(n);
  77.     PreProcess(n, maxTab , arr, 1);
  78.     PreProcess(n, minTab , arr, 0);
  79.  
  80.     int ans = 0;
  81.     for(int i = 1 ; i <= n - d + 1 ; i++){
  82.         int L = i , R = i + d - 1;
  83.         int val = Query(L , R , maxTab , 1) - Query(L , R , minTab , 0);
  84.         ans = max(ans , val);
  85.     }
  86.     cout<<ans<<endl;
  87.  
  88.     /// problem: https://www.spoj.com/problems/MOZPWS/
  89.     vector < int > ans(n - d + 1 + 1);
  90.     for(int i = 1 ; i <= n - d + 1 ; i++){
  91.         int L = i , R = i + d - 1;
  92.         ans[i] = Query(L , R , minTab , 0);
  93.     }
  94.  
  95.     PreProcess(n - d + 1 , maxTab , ans , 1);
  96.  
  97.     int q;
  98.     cin>>q;
  99.     while(q--){
  100.         int L , R;
  101.         cin>>L>>R;
  102.         R = R - d + 1;
  103.         if(L > R) cout<<"Impossible\n";
  104.         else cout<<Query(L , R , maxTab , 1);
  105.     }
  106.     return 0;
  107. }
  108.  
  109.  
  110.  
  111. LL Solve(int L , int R, vector < vector < int > >& tab)
  112. {
  113.     if(L > R) return -MAX;
  114.     Type val = Query(L , R , tab , 0);
  115.     int hieght = val.first , pos = val.second;
  116.     LL ans = 1LL*height*(R - L + 1);
  117.     /// O(1)
  118.     return max(ans , max(Solve(L , pos - 1 , tab) , Solve(pos+1 , R , tab)) );
  119. } /// O(n)
  120.  
  121. int main()
  122. {
  123.     /// problem: https://lightoj.com/problem/histogram
  124.     int n ;
  125.     cin>>n;
  126.     for(int i = 1 ; i <= n ; i++) cin>>arr[i];
  127.     vector < vector < pair < int , int > > > minTab(n+1 , vector < pair < int , int > >(22));
  128.     Cal(n);
  129.     PreProcess(n , minTab , arr, 0); /// O(nlogn)
  130.     cout<<Solve(1 , n , minTab, 1)<<endl;
  131. }
  132.  
  133.  
  134.  
  135. LL Solve(int L , int R, vector < vector < int > >& tab , int type)
  136. {
  137.     if(L > R) return 0;
  138.     Type val = Query(L , R , tab , type);
  139.     int hieght = val.first , pos = val.second;
  140.     LL con = 1LL*(pos - L + 1) * (R - pos + 1);
  141.     LL ans = 1LL*height*con;
  142.     /// O(1)
  143.     return ans + Solve(L , pos - 1 , tab , type) + Solve(pos+1 , R , tab , type) ;
  144. } /// O(n)
  145.  
  146. int main()
  147. {
  148.     /// problem: https://www.spoj.com/problems/DIFERENC/
  149.     int n ;
  150.     cin>>n;
  151.     for(int i = 1 ; i <= n ; i++) cin>>arr[i];
  152.     vector < vector < pair < int , int > > > minTab(n+1 , vector < pair < int , int > >(22)) , maxTab(n+1 , vector < Type > (22));
  153.     Cal(n);
  154.     PreProcess(n , minTab , arr, 0); /// O(nlogn)
  155.     PreProcess(n , maxTab , arr, 1); /// O(nlogn)
  156.     cout<<Solve(1 , n , maxTab, 1) - Solve(1 , n , minTab , 0)<<endl;
  157. }
  158.  
  159.  
  160.  
  161.  
  162.  
  163.  
  164.  
  165.  
  166.  
  167.  
  168.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement