fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define fbo find_by_order
  13. #define ook order_of_key
  14.  
  15. typedef long long ll;
  16. typedef pair<int,int> ii;
  17. typedef vector<int> vi;
  18. typedef long double ld; 
  19. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  20. typedef set<int>::iterator sit;
  21. typedef map<int,int>::iterator mit;
  22. typedef vector<int>::iterator vit;
  23.  
  24. ld ori[300001];
  25. ld a[300001];
  26. ld s[300001];
  27. int n;
  28.  
  29. void calcs()
  30. {
  31. 	s[0] = a[0];
  32. 	for(int i = 1; i < n; i++)
  33. 	{
  34. 		s[i] = s[i-1]+a[i];
  35. 	}
  36. }
  37.  
  38. ld sum(int l, int r)
  39. {
  40. 	if(l==0) return s[r];
  41. 	else return s[r]-s[l-1];
  42. }
  43.  
  44. const ld eps = 1e-8;
  45.  
  46. struct PBDS
  47. {
  48. 	tree<pair<ld,int>, null_type, less<pair<ld,int> >, rb_tree_tag, tree_order_statistics_node_update> t;
  49. 	int timer;
  50.  
  51. 	PBDS(){timer = 0;}
  52. 	void insert(ld x)
  53. 	{
  54. 		t.insert(mp(x, timer));
  55. 		timer++;
  56. 	}
  57.  
  58. 	int lower(ld x)
  59. 	{
  60. 		return t.order_of_key(mp(x, -1));
  61. 	}
  62.  
  63. 	void del(ld x) //make sure x exists
  64. 	{
  65. 		pair<ld,int> tmp = (*t.find_by_order(lower(x)));
  66. 		t.erase(tmp);
  67. 	}
  68.  
  69. 	int higher(ld x)
  70. 	{
  71. 		int tmp = lower(x);
  72. 		return (int(t.size()) - tmp);
  73. 	}
  74. };
  75.  
  76. int main()
  77. {
  78. 	ios_base::sync_with_stdio(0); cin.tie(0);
  79. 	int l, r; ll k; cin >> n >> l >> r >> k;
  80. 	for(int i = 0; i < n; i++) cin>>ori[i];
  81. 	ld lo = 0; ld hi = ld(1e9);
  82. 	while(hi - lo > eps)
  83. 	{
  84. 		ld mid = (lo+hi)*ld(0.5);
  85. 		for(int i = 0; i < n; i++)
  86. 		{
  87. 			a[i] = ori[i] - mid;
  88. 		}
  89. 		calcs();
  90. 		/*
  91. 		for(int i = 0; i < n; i++)
  92. 		{
  93. 			cerr<<a[i]<<' ';
  94. 		}
  95. 		cerr<<'\n';
  96. 		for(int i = 0; i < n; i++)
  97. 		{
  98. 			cerr<<s[i]<<' ';
  99. 		}
  100. 		cerr<<'\n';
  101. 		*/
  102. 		PBDS t;
  103. 		t.insert(0);
  104. 		ll cnt = 0; //count subsegments <= mid
  105. 		for(int i = l - 1; i < n; i++)
  106. 		{
  107. 			if(i >= r)
  108. 			{
  109. 				if(i>r) t.del(s[i-r-1]);
  110. 				else t.del(ld(0));
  111. 			}
  112. 			//cerr<<i<<' '<<t.t.size()<<'\n';
  113. 			cnt += t.higher(s[i]);
  114. 			t.insert(s[i-l+1]);
  115. 			//cerr<<i<<' '<<cnt<<'\n';
  116. 		}
  117. 		//cerr<<fixed<<setprecision(12)<<mid<<' '<<cnt<<'\n';
  118. 		if(cnt >= k)
  119. 		{
  120. 			hi = mid;
  121. 		}
  122. 		else
  123. 		{
  124. 			lo = mid;
  125. 		}
  126. 	}
  127. 	cout << fixed << setprecision(12) << hi << '\n';
  128. }
  129.  
Runtime error #stdin #stdout 0s 29312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/C9TYdt
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!