fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <sstream>
  4. #include <iomanip> 
  5. #include <math.h>
  6. #include <queue>
  7. #include <stack>
  8. #include <vector>
  9. #include <map>
  10. #include <set>
  11. #include <functional>
  12. #include <algorithm>
  13. #include <stdio.h>
  14. #include <stdlib.h>
  15. #pragma warning(disable:4996)
  16.  
  17. #define MOD 1000000007
  18. using namespace std;
  19.  
  20. struct area {
  21. 	int start;
  22. 	int height;
  23. };
  24. int main() {
  25. 	bool debug = 1;
  26. 	if (!debug) {
  27. 		freopen("sprinklers.in", "r", stdin);
  28. 		freopen("sprinklers.out", "w", stdout);
  29. 	}
  30. 	int n;
  31. 	cin >> n;
  32. 	vector<int>maxx(n), minn(n),t(n);
  33. 	for (int i = 0; i < n; i++) {
  34. 		int x, y; cin >> x >> y;
  35. 		t[x] = y;
  36. 	}
  37. 	vector<area>localMax;
  38. 	minn[0] = t[0];
  39. 	maxx[n - 1] = t[n - 1];
  40. 	localMax.push_back({ n - 1,t[n - 1] });
  41. 	for (int i = 1; i < n; i++) 
  42. 		 minn[i] = min(minn[i - 1], t[i]);
  43. 	for (int i = n - 2; i >= 0; i--) {
  44. 		if (t[i] < maxx[i + 1]) maxx[i] = maxx[i + 1];
  45. 		else {
  46. 			maxx[i] = t[i];
  47. 			localMax.push_back({ i, t[i] });
  48. 		}
  49. 	}
  50. 	reverse(localMax.begin(), localMax.end());
  51. 	long long ans = 0;
  52. 	int curr = 0;
  53. 	for (int i = 0; i < n - 1; i++) {
  54. 		while (curr < localMax.size() && localMax[curr].start <= i)curr++;
  55. 		if (curr == localMax.size())break;
  56. 		for (int j = curr; j < localMax.size(); j++) {
  57. 			long long h = localMax[j].height - minn[i],range=localMax[j].start-i;
  58. 			if (h <= 0)break;
  59. 			ans += range*h * (h + 1) / 2;
  60. 			if (j == curr)continue;
  61. 			long long x = localMax[j - 1].start - i;
  62. 			ans -= (h*(h + 1))*x/2;
  63. 		}
  64. 		ans %= MOD;
  65. 	}
  66. 	cout << ans << "\n";
  67. 	return 0;
  68. }
Success #stdin #stdout 0s 4556KB
comments (?)
stdin
copy 
5
0 4
1 1
2 2
3 0
4 3
stdout
copy 
21
https://ideone.com/3rQUoq
language:
C++14 (gcc 8.3)
created:
6 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!