fork download
copy 
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <list>
  4. #include <map>
  5. #include <set>
  6. #include <deque>
  7. #include <queue>
  8. #include <stack>
  9. #include <bitset>
  10. #include <algorithm>
  11. #include <functional>
  12. #include <numeric>
  13. #include <utility>
  14. #include <sstream>
  15. #include <iostream>
  16. #include <iomanip>
  17. #include <cstdio>
  18. #include <cmath>
  19. #include <cstdlib>
  20. #include <cctype>
  21. #include <string>
  22. #include <cstring>
  23. #include <cstdio>
  24. #include <cmath>
  25. #include <cstdlib>
  26. #include <ctime>
  27. #include <string.h>
  28. #include <fstream>
  29. #include <cassert>
  30. #include <unordered_map>
  31. #include <ext/pb_ds/assoc_container.hpp>
  32. #include <ext/pb_ds/tree_policy.hpp>
  33. //#include <sys/resource.h>
  34.  
  35. using namespace std;
  36. using namespace __gnu_pbds;
  37.  
  38. #ifdef loc
  39.  
  40. template<class T, class U> ostream &operator<<
  41.   (ostream &out,
  42.    const pair<T, U> &a) {
  43.   out << "[" << a.first << " " << a.second << "]";
  44.   return out;
  45. }
  46.  
  47. template<class T>
  48.   ostream &operator<<(ostream &out,
  49.                       const vector<T> &a) {
  50.   out << "[ ";
  51.   for(auto &it : a) {
  52.     out << it << " ";
  53.   }
  54.   out << "]";
  55.   return out;
  56. }
  57.  
  58. template<class T> ostream &operator<<(ostream &out, const set<T> &a) {
  59.     out << "[ ";
  60.     for(auto &it : a) {
  61.       out << it << " ";
  62.     }
  63.     out << "]";
  64.     return out;
  65.   }
  66.  
  67. template<class T>
  68.   ostream &operator<<(ostream &out,
  69.                       const multiset<T> &a) {
  70.   out << "[ ";
  71.   for(auto &it : a) {
  72.     out << it << " ";
  73.   }
  74.   out << "]";
  75.   return out;
  76. }
  77.  
  78. template<class T, class U>
  79.   ostream &operator<<(ostream &out,
  80.                       const map<T, U> &a) {
  81.   for(auto &it : a) {
  82.     out << it.first << " -> " << it.second << " | ";
  83.   }
  84.   return out;
  85. }
  86.  
  87. template<class T, class U>
  88.   ostream &operator<<(ostream &out,
  89.                       const multimap<T, U> &a) {
  90.   for(auto &it : a) {
  91.     out << it.first << " -> " << it.second << " | ";
  92.   }
  93.   return out;
  94. }
  95.  
  96. #define pra(a, n) cerr << #a << " : "; for(int i = 0; i <= n; ++i) cerr << a[i] << " "; cerr << endl;
  97.  
  98. #define praa(a, n, m) cerr << #a << " : " << endl; for(int i = 0; i <= n; ++i) { for(int j = 0; j <= m; ++j) cerr << a[i][j] << " "; cerr << endl; }
  99.  
  100. #define pr(...) __f(#__VA_ARGS__, __VA_ARGS__)
  101.  
  102. #define prl() cerr << __LINE__ << ": " << __PRETTY_FUNCTION__ << endl;
  103.  
  104. template <typename Arg1>
  105. void __f(const char *name, Arg1 &&arg1) {
  106.   cerr << name << " : " << arg1 << std::endl;
  107. }
  108.  
  109. template <typename Arg1, typename... Args>
  110. void __f(const char *names, Arg1 &&arg1,
  111.          Args &&... args) {
  112.   const char *comma = strchr(names + 1, ',');
  113.   cerr.write(names,
  114.              comma - names) << " : " << arg1 << " | ";
  115.   __f(comma + 1, args...);
  116. }
  117.  
  118. #define gc getchar
  119.  
  120. #else
  121.  
  122. #define pr(...)
  123. #define pra(a, n)
  124. #define praa(a, n, m)
  125. #define prl()
  126. #define gc getchar
  127. #define endl '\n'
  128.  
  129. #endif
  130.  
  131. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
  132. ordered_set;
  133. typedef long long ll;
  134. typedef vector<int> vi;
  135. typedef vector<vector<int>> vvi;
  136. typedef pair<int, int> pii;
  137. typedef vector<pair<int, int>> vpii;
  138. typedef vector<vector<pair<int, int>>> vvpii;
  139. typedef vector<ll> vl;
  140. typedef vector<vector<ll>>vvl;
  141. typedef pair<ll, ll> pll;
  142. typedef vector<pair<ll, ll>> vpll;
  143. typedef vector<vector<pair<ll, ll>>> vvpll;
  144.  
  145. template<typename T, typename U> static void amin(
  146.   T &x, U y) {
  147.   if(y < x) {
  148.     x = y;
  149.   }
  150. }
  151.  
  152. template<typename T, typename U> static void amax(
  153.   T &x, U y) {
  154.   if(x < y) {
  155.     x = y;
  156.   }
  157. }
  158.  
  159. #define inc_stack_limit const rlim_t kStackSize = 64 * 1024 * 1024; struct rlimit rl; rl.rlim_cur = kStackSize; setrlimit(RLIMIT_STACK, &rl);
  160. #define sz(a) int((a).size())
  161. #define all(a) (a).begin(),(a).end()
  162. #define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
  163. #define pb push_back
  164. #define eb emplace_back
  165. #define mp make_pair
  166. #define F first
  167. #define S second
  168. #define rep(i, s, n)  for(int i = s; i <= (n); ++i)
  169. #define rev(i, n, s)  for(int i = (n); i >= s; --i)
  170. #define fore(x, a) for(auto &&x : a)
  171. #define fill(a, x) memset((a), (x), sizeof(a))
  172. const double eps = 1e-6;
  173. #define tcase int __T; cin >> __T; rep(Tc, 1, __T)
  174. #define ass(n, l, r) assert(n >= l and n <= r)
  175. #define mod 1000000007
  176.  
  177. #define FOR(i, a, b) for (int i = (a); i < (b); ++i)
  178. #define REP(i, n) FOR(i, 0, n)
  179. typedef long long llint;
  180.  
  181. inline int add(int a, int b, int m = mod) {
  182.   a += b;
  183.   if(a >= m) {
  184.     a -= m;
  185.   }
  186.   if(a < 0) {
  187.     a += m;
  188.   }
  189.   return a;
  190. }
  191.  
  192. inline int mul(int a, int b, int m = mod) {
  193.   int ret = (int)(((ll)a * (ll)b) % m);
  194.   if(ret < 0) {
  195.     ret += m;
  196.   }
  197.   return ret;
  198. }
  199.  
  200. ll po(ll a, ll b, ll m = mod) {
  201.   ll res = 1;
  202.   a %= m;
  203.   //assert(b >= 0);
  204.   for(; b; b >>= 1) {
  205.     if(b & 1) {
  206.       res = (res * a) % m;
  207.     }
  208.     a = (a * a) % m;
  209.   }
  210.   return res;
  211. }
  212.  
  213. inline int ri() {
  214.   int c = gc();
  215.   int ret = 0;
  216.   while(c < '0' || c > '9') {
  217.     c = gc();
  218.   }
  219.   while(c >= '0' && c <= '9') {
  220.     ret = 10 * ret + c - 48;
  221.     c = gc();
  222.   }
  223.   return ret;
  224. }
  225.  
  226. #define N 200005
  227.  
  228. //actual code starts here:
  229. int a[N];
  230. bool b[N];
  231.  
  232. int main() {
  233.   boost;
  234.   int n;
  235.   cin >> n;
  236.   rep(i, 1, n) {
  237.     cin >> a[i];
  238.   }
  239.   int mx = 0;
  240.   int mn = a[1];
  241.   rep(i, 2, n) {
  242.     mx = max(mx, a[i] - mn);
  243.     mn = min(mn, a[i]);
  244.   }
  245.   int nm = a[1];
  246.   rep(i, 2, n) {
  247.     if(a[i] - nm == mx) {
  248.       b[i] = 1;
  249.     }
  250.     nm = min(nm, a[i]);
  251.   }
  252.   ll pr = -mod;
  253.   int four = 0;
  254.   int ans = 0;
  255.   rev(i, n, 1) {
  256.     if(b[i]) {
  257.       if(a[i] > pr) {
  258.         four = 0;
  259.         pr = a[i];
  260.       }
  261.       four++;
  262.     }
  263.     if(pr - a[i] == mx) {
  264.       if(four) {
  265.         ans++;
  266.         four--;
  267.       }
  268.     }
  269.   }
  270.   cout << ans << endl;
  271.   return 0;
  272. }
  273.  
Success #stdin #stdout 0s 4440KB
comments (?)
stdin
copy 
6
2 4 4 2 2 4
stdout
copy 
2
https://ideone.com/Jstn8Z
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!