fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long lld;
  4. const double PI = 3.14159265359;
  5.  
  6. const int MN = 1e5 + 10;
  7. struct Cake
  8. {
  9. 	int id;
  10. 	lld v;
  11. 	Cake(){}
  12. 	Cake(int _id, lld _v): id(_id),v(_v){}
  13.  
  14. 	bool operator < (const Cake& rhs) const
  15. 	{
  16. 		return v < rhs.v;
  17. 	}
  18. };
  19.  
  20. int n;
  21. Cake C[MN];
  22.  
  23. double s[MN * 4];
  24.  
  25. double query(int x, int y, int id = 1, int l = 0, int r = n - 1)
  26. {
  27. 	if(y < l || r < x) return 0.0;
  28. 	if(x <= l && r <= y) return s[id];
  29. 	int mid = (l + r) >> 1;
  30. 	return max(query(x, y, id << 1, l, mid), query(x, y, id << 1 | 1, mid + 1, r));
  31. }
  32.  
  33. void put(int pos, double val, int id = 1, int l = 0, int r = n - 1)
  34. {
  35. 	if(l == r){
  36. 		s[id] = val;
  37. 		return;
  38. 	}
  39. 	int mid = (l + r) >> 1;
  40. 	if(pos <= mid){
  41. 		put(pos, val, id << 1, l, mid);
  42. 	}else{
  43. 		put(pos, val, id << 1 | 1, mid + 1, r);
  44. 	}
  45. 	s[id] = max(s[id << 1], s[id << 1 | 1]);
  46. }
  47.  
  48. int main()
  49. {
  50. 	cin >> n;
  51. 	vector<lld> ca;
  52. 	for(int i = 0; i < n; ++i){
  53. 		int r, h;
  54. 		cin >> r >> h;
  55. 		C[i].id = i;
  56. 		C[i].v = (lld)r * r * h;
  57. 	}
  58. 	sort(C, C + n);
  59.  
  60. 	queue<pair<double, int>> q;
  61. 	for(int i = 0; i < n;){
  62. 		do{
  63. 			double x = query(0, C[i].id);
  64. 			q.push(make_pair(x + PI * C[i].v, C[i].id));
  65. 			++i;
  66. 		}while(i < n && C[i].v == C[i - 1].v);
  67. 		while(!q.empty()){
  68. 			put(q.front().second, q.front().first);
  69. 			q.pop();
  70. 		}
  71. 	}
  72. 	cout << fixed;
  73. 	cout << setprecision(10);
  74. 	cout << s[1] << '\n';
  75. }
  76.  
Success #stdin #stdout 0s 7760KB
comments (?)
stdin
copy 
4
1 1
9 7
1 4
10 7
stdout
copy 
3983.5394847521
https://ideone.com/WrdiFa
codeforces round 343 div2 D
language:
C++14 (gcc 8.3)
created:
8 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!