fork download 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include <algorithm>
  6. using namespace std;
  7. #define re(i, n) for (int i=0; i<n; i++)
  8. #define re1(i, n) for (int i=1; i<=n; i++)
  9. #define re2(i, l, r) for (int i=l; i<r; i++)
  10. #define re3(i, l, r) for (int i=l; i<=r; i++)
  11. #define rre(i, n) for (int i=n-1; i>=0; i--)
  12. #define rre1(i, n) for (int i=n; i>0; i--)
  13. #define rre2(i, r, l) for (int i=r-1; i>=l; i--)
  14. #define rre3(i, r, l) for (int i=r; i>=l; i--)
  15. #define ll long long
  16. const int MAXN = 100010, INF = ~0U >> 2;
  17. struct sss {
  18.     int v, No;
  19. 	bool operator< (sss s0) const {return v < s0.v;}
  20. } A[MAXN];
  21. int n;
  22. bool F[MAXN];
  23. ll res1, res2;
  24. void init()
  25. {
  26. 	scanf("%d", &n); re(i, n) {scanf("%d", &A[i].v); A[i].No = i;}
  27. }
  28. void solve()
  29. {
  30. 	if (n == 1) {res1 = 0; res2 = 1; return;}
  31. 	int v0 = A[0].v, v1 = A[n - 1].v, tmp; if (v0 > v1) {tmp = v0; v0 = v1; v1 = tmp;}
  32. 	sort(A, A + n);
  33. 	int x = -1, s = 1, No0; ll sum = 0;
  34. 	re(i, n) {
  35. 		if (A[i].v > x) {sum += (ll) (A[i].v - x) * s; x = A[i].v;}
  36. 		No0 = A[i].No;
  37. 		if (No0 && No0 < n - 1 && !F[No0 - 1] && !F[No0 + 1]) s++;
  38. 		else if (No0 && No0 < n - 1 && F[No0 - 1] && F[No0 + 1]) s--;
  39. 		else if (!No0 && F[1]) s--;
  40. 		else if (No0 == n - 1 && F[n - 2]) s--;
  41. 		F[No0] = 1;
  42. 	}
  43. 	res1 = sum - (v0 + 1); res2 = v1 - v0 + 1;
  44. }
  45. void pri()
  46. {
  47. 	cout << res1 << endl << res2 << endl;
  48. }
  49. int main()
  50. {
  51.     init();
  52.     solve();
  53.     pri();
  54.     return 0;
  55. }
  56.  
  57.  
Success #stdin #stdout 0.01s 3564KB
comments (?)
stdin 
4
1
1
2
2
stdout 
1
2
https://ideone.com/daKifx
language:
C++ (gcc 8.3)
created:
12 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!