Guest User

Untitled

a guest
Nov 6th, 2018
47
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 1e6+10;
  5. int lt[N];
  6. int rt[N];
  7. int hsh[N];
  8. int main(){
  9.     int t;
  10.     cin >> t;
  11.     assert(1<=t && t <= 10);
  12.     while(t--){
  13.         int n, m;
  14.         cin >> n >> m;
  15.         assert(n >= 1 && n <= 1000000);
  16.         assert(m >= 2  && m <= 1000000);
  17.         for(int i = 0; i <= n; ++i){
  18.             hsh[i] = 0;
  19.         }
  20.         int x;
  21.         for(int i = 0; i < m; ++i){
  22.             cin >> x;
  23.             hsh[x]++;
  24.         }
  25.        
  26.         stack <int> s;
  27.         for(int i = 0; i <= n; ++i){
  28.             while(!s.empty() && hsh[s.top()] > hsh[i]){
  29.                 rt[s.top()] = i;
  30.                 s.pop();
  31.             }
  32.             s.push(i);
  33.         }
  34.         while(!s.empty()){
  35.             rt[s.top()] = n+1;
  36.             s.pop();
  37.         }
  38.         for(int i = n; i >= 0; --i){
  39.             while(!s.empty() && hsh[s.top()] > hsh[i]){
  40.                 lt[s.top()] = i;
  41.                 s.pop();
  42.             }
  43.             s.push(i);
  44.         }
  45.         while(!s.empty()){
  46.             lt[s.top()] = -1;
  47.             s.pop();
  48.         }
  49.         long long int ans = 0;
  50.         for(int i = 0; i <= n; ++i){
  51.         //  cout << lt[i] << " " << rt[i] << endl;
  52.             ans = max(hsh[i] * 1LL * (rt[i] - lt[i] - 1), ans);
  53.         }
  54.         cout << ans << endl;
  55.     }
  56. }
RAW Paste Data