fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. #define INF 1000010000
  4. #define nl '\n'
  5. #define pb push_back
  6. #define ppb pop_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define pii pair<int,int>
  11. #define pdd pair<double,double>
  12. #define all(c) (c).begin(), (c).end()
  13. #define SORT(c) sort(all(c))
  14. #define sz(c) (c).size()
  15. #define rep(i,n) for( int i = 0; i < n; ++i )
  16. #define repi(i,n) for( int i = 1 ; i <= n; ++i )
  17. #define repn(i,n) for( int i = n - 1 ; i >= 0 ; --i )
  18. #define repf(j,i,n) for( int j = i ; j < n ; ++j )
  19. #define die(s) {std::cout << s << nl;}
  20. #define dier(s) {std::cout << s; return 0;}
  21. #define dbg(var) {std::cout << #var << "  = " << var << nl;}
  22. #define vi vector<int>
  23. typedef long long ll;
  24.  
  25. using namespace std;
  26.  
  27. struct rect
  28. {
  29. 	pii bl, tr;
  30. 	int val;
  31. };
  32.  
  33. constexpr int MAX_X = 1e4 + 5;
  34.  
  35. int main() {
  36. 	ios_base::sync_with_stdio(false);
  37. 	cin.tie(NULL);
  38. 	cout.precision(0); 
  39.  
  40. 	int n;
  41. 	cin >> n;
  42.  
  43. 	vector<rect> v;
  44. 	rep(i , n)
  45. 	{
  46. 		v.emplace_back();
  47. 		cin >> v.back().bl.fi >> v.back().bl.se >> v.back().tr.fi >> v.back().tr.se >> v.back().val;
  48. 	}
  49.  
  50. 	struct state
  51. 	{
  52. 		int type;
  53. 		int x;
  54. 		int i;
  55. 	};
  56.  
  57. 	vector<state> states;
  58. 	rep(i , n)
  59. 	{
  60. 		state begin, end;
  61.  
  62. 		begin.type = 1;
  63. 		end.type = -1;
  64.  
  65. 		begin.x = v[i].bl.fi;
  66. 		end.x = v[i].tr.fi;
  67.  
  68. 		begin.i = end.i = i;
  69.  
  70. 		states.pb(begin);
  71. 		states.pb(end);
  72. 	}
  73.  
  74. 	sort(all(states) , [](auto& a , auto& b)
  75. 	{
  76. 		return a.x < b.x || (a.x == b.x && a.type < b.type);	
  77. 	});
  78.  
  79. 	vi grid(MAX_X);
  80. 	int l = -1;
  81. 	int ans = 0; 
  82. 	int cnt = 0;
  83. 	int p = 0;
  84.  
  85. 	while(p < states.size())
  86. 	{
  87. 		int cur_x = states[p].x;
  88. 		int w = cur_x - l;
  89. 		rep(i , MAX_X)
  90. 		{
  91. 			if(ans == grid[i])
  92. 			{
  93. 				cnt += w;
  94. 			}
  95. 			else if(grid[i] > ans)
  96. 			{ 
  97. 				ans = grid[i];
  98. 				cnt = w;
  99. 			}
  100. 		}
  101.  
  102. 		vi tmp(MAX_X);
  103. 		do
  104. 		{
  105. 			if(p >= states.size()) break;
  106. 			if(states[p].x != cur_x) break;
  107. 			if(states[p].type != -1) break;
  108. 			tmp[v[states[p].i].bl.se] -= v[states[p].i].val;
  109. 			tmp[v[states[p].i].tr.se] += v[states[p].i].val;
  110. 			++p;
  111. 		}
  112. 		while(p < states.size());
  113.  
  114. 		do
  115. 		{
  116. 			if(p >= states.size()) break;
  117. 			if(states[p].x != cur_x) break;
  118. 			if(states[p].type  != 1) break;
  119. 			tmp[v[states[p].i].bl.se] += v[states[p].i].val;
  120. 			tmp[v[states[p].i].tr.se] -= v[states[p].i].val;
  121. 			++p;
  122. 		}
  123. 		while(p < states.size());
  124.  
  125. 		rep(i , MAX_X)
  126. 		{
  127. 			if(i > 0) tmp[i] += tmp[i - 1];
  128. 			grid[i] += tmp[i];
  129. 		}
  130.  
  131. 		l = cur_x;
  132. 	}
  133.  
  134. 	cout << ans << endl;
  135.  
  136. 	return 0;
  137. }
Success #stdin #stdout 0s 15360KB
comments (?)
stdin
copy 
5
21 46 38 56 13
26 28 47 38 8
18 32 38 38 5
31 35 42 51 8
39 31 45 38 5
stdout
copy 
21
https://ideone.com/82XDr3
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!