SHARE
TWEET

Untitled

a guest Jun 16th, 2017 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _USE_MATH_DEFINES
  2. #define _CRT_SECURE_NO_WARNINGS
  3.  
  4. #include <bits/stdc++.h>
  5.  
  6. using namespace std;
  7.  
  8. #define forn(i, n) for(int i = 0; i < n; i++)
  9. #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
  10.  
  11. #define sqr(a) ((a) * (a))
  12. #define sz(a) int(a.size())
  13. #define all(a) a.begin(), a.end()
  14.  
  15. #define x first
  16. #define y second
  17. #define pb push_back
  18. #define mp make_pair
  19.  
  20. template<class A, class B> ostream& operator <<(ostream &out, const pair<A, B> &p) {
  21.     return out << "(" << p.x << ", " << p.y << ")";
  22. }
  23.  
  24. template<class T> ostream& operator <<(ostream &out, const vector<T> &v) {
  25.     out << "[";
  26.     forn(i, sz(v) - 1)
  27.         out << v[i] << ", ";
  28.     return out << v.back() << "]";
  29. }
  30.  
  31. typedef long double ld;
  32. typedef long long li;    
  33. typedef pair <int, int> pt;
  34.  
  35. const ld EPS = 1e-9;
  36. const int INF = int(1e9);
  37. const li INF64 = li(1e18);
  38.  
  39. const int N = 100 * 1000 + 11;
  40.  
  41. int n;
  42. int a[N];
  43. pt mnl[N], mnr[N];
  44.  
  45. inline bool read() {
  46.     if(scanf("%d", &n) != 1)
  47.         return false;
  48.     forn(i, n) scanf("%d", &a[i]);
  49.     return true;
  50. }
  51.  
  52. struct triplet{
  53.     int x, y, z;
  54. };
  55.  
  56. bool operator ==(const triplet &a, const triplet &b){
  57.     return a.x == b.x && a.y == b.y && a.z == b.z;
  58. }
  59.  
  60. void norm(triplet &p){
  61.     if (p.y < p.x)
  62.         swap(p.y, p.x);
  63.     if (p.z < p.x)
  64.         swap(p.z, p.x);
  65.     if (p.z < p.y)
  66.         swap(p.z, p.y);
  67. }
  68.  
  69.  
  70. void solve() {
  71.     nth_element(a, a + 2, a + n);
  72.     triplet mns = {a[0], a[1], a[2]};
  73.     norm(mns);
  74.  
  75.     mnl[0] = mp(a[0], 1);
  76.     mnr[n - 1] = mp(a[n - 1], 1);
  77.     for(int i = 1; i < n; i++) {
  78.         if(a[i] < mnl[i - 1].x)
  79.             mnl[i] = mp(a[i], 1);
  80.         else if(a[i] == mnl[i - 1].x)
  81.             mnl[i] = mp(mnl[i - 1].x, mnl[i - 1].y + 1);
  82.         else
  83.             mnl[i] = mnl[i - 1];
  84.     }
  85.     for(int i = n - 2; i >= 0; i--) {
  86.         if(a[i] < mnr[i + 1].x)
  87.             mnr[i] = mp(a[i], 1);
  88.         else if(a[i] == mnr[i + 1].x)
  89.             mnr[i] = mp(mnr[i + 1].x, mnr[i + 1].y + 1);
  90.         else
  91.             mnr[i] = mnr[i + 1];
  92.     }
  93.    
  94.     li ans = 0;
  95.     triplet cmns;
  96.     for(int i = 1; i < n - 1; i++) {
  97.         cmns = {mnl[i - 1].x, a[i], mnr[i + 1].x};
  98.         norm(cmns);
  99.         if(mns == cmns)
  100.             ans += mnl[i - 1].y * 1ll * mnr[i + 1].y;
  101.     }
  102.     printf("%lld\n", ans);
  103. }
  104.  
  105.  
  106. int main() {
  107. #ifdef _DEBUG
  108.     int t = 0;
  109.     freopen("input.txt", "r", stdin);
  110. //  freopen("output.txt", "w", stdout);
  111. #endif
  112.  
  113.     cout << fixed << setprecision(15);
  114.  
  115.     while(read()) {
  116.         solve();
  117.        
  118. #ifdef _DEBUG
  119.         cerr << "TIME = " << clock() - t << endl;
  120.         t = clock();
  121. #endif
  122.     }
  123.    
  124.     return 0;
  125. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top