Advertisement
ekanshlohiya98

Sum of max and min in all subarrays

Jul 7th, 2022
620
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.60 KB | None
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef long double ld;
  5. #define pb push_back
  6. #define mp make_pair
  7. #define vpll vector<pair<ll,ll>>
  8. #define vll vector<ll>
  9. #define mpll map<ll,ll>
  10. #define all(x) x.begin(),x.end()
  11. #define sortall(x) sort(x.begin(),x.end())
  12. #define line cout<<'\n'
  13. #define fo(i,n) for(int i=0;i<n;i++)
  14. #define foe(i,a,n) for(int i=a;i<n;i++)
  15. #define fr(i,n) for(int i=n-1;i>=0;i--)
  16. #define cy cout<<"YES"<<endl
  17. #define cn cout<<"NO"<<endl
  18. #define debug(x) cout<<x<<endl
  19. #define print(x) cout<<x<<" "
  20. #define deb(x,y) cout<<x<<" "<<y<<endl
  21. #define MOD 1000000007
  22. const int N1=100001;
  23. bool isPrime[N1];
  24. void sieve()
  25. {
  26.     memset(isPrime, true, sizeof(isPrime));
  27.     for (int p = 2; p * p <= N1; p++)
  28.     {
  29.         if (isPrime[p] == true)
  30.         {
  31.             for (int i = p * p; i <= N1; i += p)
  32.                 isPrime[i] = false;
  33.         }
  34.     }
  35. }
  36. long long power(long long a, long long b) {
  37.     if (b == 0)
  38.         return 1;
  39.     long long res = power(a, b / 2);
  40.     if (b % 2)
  41.         return res * res * a;
  42.     else
  43.         return res * res;
  44. }
  45. /*====================================================================================*/
  46.  
  47. int sumMaxMin(vector<int> &a,int k)
  48. {
  49.     deque<int> dqmin,dqmax;
  50.     int n=a.size();
  51.     int ans=0;
  52.     for(int i=0;i<k;i++)
  53.     {
  54.         //first window
  55.         //remove the elements which cant be the candidate
  56.         while(!dqmin.empty() and a[dqmin.back()]>=a[i]) dqmin.pop_back();
  57.         while(!dqmax.empty() and a[dqmax.back()]<=a[i]) dqmax.pop_back();
  58.         dqmin.push_back(i);
  59.         dqmax.push_back(i);
  60.     }
  61.     // print(a[dqmax.front()]); print(a[dqmin.front()]);
  62.     ans+=a[dqmin.front()]+a[dqmax.front()];
  63.     for(int i=k;i<n;i++)
  64.     {
  65.         //remove out of window elements
  66.         while(!dqmin.empty() and dqmin.front()<i-k+1) dqmin.pop_front();
  67.         while(!dqmax.empty() and dqmax.front()<i-k+1) dqmax.pop_front();
  68.  
  69.         //remove the elements which cant be the candidate
  70.         while(!dqmin.empty() and a[dqmin.back()]>=a[i]) dqmin.pop_back();
  71.         while(!dqmax.empty() and a[dqmax.back()]<=a[i]) dqmax.pop_back();
  72.         dqmin.push_back(i);
  73.         dqmax.push_back(i);
  74.         // print(a[dqmax.front()]); print(a[dqmin.front()]);
  75.         ans+=a[dqmin.front()]+a[dqmax.front()];
  76.     }
  77.     return ans;
  78. }
  79.  
  80. int main()
  81. {
  82.     ios_base::sync_with_stdio(false);
  83.     cin.tie(NULL);
  84.     ll t=1;
  85.     cin>>t;
  86.  
  87.     while(t--)
  88.     {
  89.         int n,k; cin>>n>>k;
  90.         vector<int> a(n);
  91.         for(int i=0;i<n;i++) cin>>a[i];
  92.         cout<<sumMaxMin(a,k);
  93.     }
  94. }
  95.  
Advertisement
RAW Paste Data Copied
Advertisement