fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. //#pragma GCC optimize ("O3")
  5. //#pragma GCC target ("sse4")
  6.  
  7. #define SZ(x) ((int)x.size())
  8. #define ALL(V) V.begin(), V.end()
  9. #define L_B lower_bound
  10. #define U_B upper_bound
  11. #define pb push_back
  12.  
  13. using namespace std;
  14. template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
  15. template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
  16. const int MAXN = (1 << 20);
  17. const int OFFSET = (int)3e5 + 152;
  18.  
  19. int n, k;
  20. string s;
  21.  
  22. void read()
  23. {
  24. 	cin >> n >> k >> s;
  25. }
  26.  
  27. int psum[MAXN];
  28. int dp[MAXN];
  29.  
  30. int tr[4 * MAXN];
  31. multiset<int> P[OFFSET * 2];
  32.  
  33. void init(int l, int r, int idx)
  34. {
  35. 	if(l == r)
  36. 	{
  37. 		tr[idx] = (int)1e9;
  38. 		return;
  39. 	}
  40.  
  41. 	int mid = (l + r) >> 1;
  42. 	init(l, mid, 2 * idx + 1);
  43. 	init(mid + 1, r, 2 * idx + 2);
  44.  
  45. 	tr[idx] = min(tr[2 * idx + 1], tr[2 * idx + 2]);
  46. }
  47.  
  48. void add(int pos, int val, int l, int r, int idx)
  49. {
  50. 	if(l == r)
  51. 	{
  52. 		P[OFFSET + pos].insert(val);
  53. 		tr[idx] = *P[OFFSET + pos].begin();
  54. 		return;
  55. 	}
  56.  
  57. 	int mid = (l + r) >> 1;
  58. 	if(mid < pos) add(pos, val, mid + 1, r, 2 * idx + 2);
  59. 	else add(pos, val, l, mid, 2 * idx + 1);
  60.  
  61. 	tr[idx] = min(tr[2 * idx + 1], tr[2 * idx + 2]);
  62. }
  63.  
  64. void rem(int pos, int val, int l, int r, int idx)
  65. {
  66. 	if(l == r)
  67. 	{
  68. 		P[OFFSET + pos].erase(P[OFFSET + pos].find(val));
  69. 		tr[idx] = P[OFFSET + pos].empty() ? (int)1e9 : *P[OFFSET + pos].begin();
  70. 		return;
  71. 	}
  72.  
  73. 	int mid = (l + r) >> 1;
  74. 	if(mid < pos) rem(pos, val, mid + 1, r, 2 * idx + 2);
  75. 	else rem(pos, val, l, mid, 2 * idx + 1);
  76.  
  77. 	tr[idx] = min(tr[2 * idx + 1], tr[2 * idx + 2]);
  78. }
  79.  
  80. int query(int ql, int qr, int l, int r, int idx)
  81. {
  82. 	if(qr < l || r < ql) return (int)1e9;
  83. 	if(ql <= l && r <= qr)
  84. 		return tr[idx];
  85.  
  86. 	int mid = (l + r) >> 1;
  87. 	return min(query(ql, qr, l, mid, 2 * idx + 1), query(ql, qr, mid + 1, r, 2 * idx + 2));
  88. }
  89.  
  90. void solve()
  91. {
  92. 	for(int i = 1; i <= n; i++)
  93. 		psum[i] = psum[i - 1] + (s[i - 1] == 'G' ? 1 : -1);
  94.  
  95. 	int N = n + 42;
  96. 	init(-N, N, 0);
  97. 	add(0, 0, -N, N, 0);
  98. 	for(int i = 1; i <= n; i++)
  99. 	{
  100. 		dp[i] = query(-N, psum[i], -N, N, 0) + 1;
  101. 		chkmin(dp[i], query(psum[i] + 1, N, -N, N, 0));
  102.  
  103. 		add(psum[i], dp[i], -N, N, 0);
  104. 		if(i >= k) 
  105. 			rem(psum[i - k], dp[i - k], -N, N, 0);
  106. 	}
  107.  
  108. 	cout << dp[n] << endl;
  109. }
  110.  
  111. int main()
  112. {
  113. 	freopen("redistricting.in", "r", stdin);
  114. 	freopen("redistricting.out", "w", stdout);
  115. 	ios_base::sync_with_stdio(false);
  116. 	cin.tie(NULL);
  117.  
  118. 	read();
  119. 	solve();
  120. 	return 0;
  121. }
  122.  
  123.  
Runtime error #stdin #stdout #stderr 0s 67968KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::ios_base::failure[abi:cxx11]'
  what():  basic_filebuf::underflow error reading the file: iostream error
https://ideone.com/itkrux
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!