Guest User

Untitled

a guest
Nov 6th, 2018
61
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  #define rep(i,a,b) for (i=a;i<b;i++)
  3.  #define rep2(i,a,b) for (i=a;i>=b;i--)
  4.  #define mod 1000000007
  5.  //#include<boost/multiprecision/cpp_int.hpp>
  6.  //using namespace boost::multiprecision;
  7.  #define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
  8.  #define INF  1e9+5
  9.  #define f first
  10.  #define s second
  11.  #define endl '\n'
  12.  #define ll long long
  13.  #define ii pair <int,int>
  14.  #define pll pair <ll,ll>
  15.  #define vi vector <int>
  16.  #define vl vector <ll>
  17.  #define vvi vector < vi >
  18.  #define vii vector < ii >
  19.  #define vvii vector < vii >
  20.  #define vll vector < ll >
  21.  #define vb  vector <bool>
  22.  #define pb push_back
  23.  #define mk make_pair
  24.  #define sz(a) a.size()
  25.  #define all(a) a.begin(),a.end()
  26.  #define rall(a) a.rbegin(),a.rend()
  27.  #define cset(a) __builtin_popcountll(a)
  28.  #include<string>
  29.  #include<sstream>
  30.  using namespace std;
  31.  int a[1000001];
  32.  int main()
  33.  {
  34.     FIO;
  35.     int t, n, m, i, top_i, x;
  36.     ll maxx, cur_maxx;
  37.     cin>>t;
  38.     while(t--)
  39.     {
  40.         cin>>n>>m;
  41.  
  42.         memset(a,0,sizeof(a));
  43.         rep(i,0,m)
  44.         {
  45.             cin>>x;
  46.             a[x]++;
  47.         }
  48.         stack<int>ss;
  49.         i = 0;
  50.         maxx = 0;
  51.         while(i <= n)
  52.         {
  53.             if( ss.empty() || a[ss.top()] <= a[i])
  54.             {  ss.push(i);
  55.                i++;
  56.             }
  57.             else
  58.             {
  59.                 top_i = ss.top();
  60.                 ss.pop();
  61.                 if( ss.empty())
  62.                   cur_maxx = a[top_i]*i;
  63.                 else
  64.                   cur_maxx = a[top_i]*(i - ss.top() - 1);
  65.                 if( cur_maxx > maxx)
  66.                  maxx = cur_maxx;
  67.             }
  68.         }
  69.         while( !ss.empty())
  70.         {
  71.                top_i = ss.top();
  72.                 ss.pop();
  73.                 if( ss.empty())
  74.                   cur_maxx = a[top_i]*i;
  75.                 else
  76.                   cur_maxx = a[top_i]*(i - ss.top() - 1);
  77.                 if( cur_maxx > maxx)
  78.                  maxx = cur_maxx;
  79.         }
  80.         cout<<maxx<<endl;
  81.     }
  82.     return 0;
  83.  }
RAW Paste Data