fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // orz laofudasuan
  5. // modified
  6.  
  7. namespace io {
  8. 	const int SIZE = (1 << 21) + 1;
  9. 	char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
  10. 	// getchar
  11. 	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
  12. 	// print the remaining part
  13. 	inline void flush () {
  14. 		fwrite (obuf, 1, oS - obuf, stdout);
  15. 		oS = obuf;
  16. 	}
  17. 	inline char getc() { return gc(); }
  18. 	// putchar
  19. 	inline void putc (char x) {
  20. 		*oS ++ = x;
  21. 		if (oS == oT) flush ();
  22. 	}
  23. 	// input a signed integer
  24. 	template <class I>
  25. 	inline void gi (I &x) {
  26. 		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
  27. 		for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
  28. 	}
  29. 	// print a signed integer
  30. 	template <class I>
  31. 	inline void print (I x) {
  32. 		if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
  33. 		while (x) qu[++ qr] = x % 10 + '0',  x /= 10;
  34. 		while (qr) putc (qu[qr --]);
  35. 	}
  36. 	//no need to call flush at the end manually!
  37. 	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
  38. }
  39. using io::gi;
  40. using io::putc;
  41. using io::print;
  42. using io::getc;
  43.  
  44. const int MAXN = 3.1e5;
  45. int N, K;
  46. char P[MAXN];
  47. pair<pair<int, int>, int> dq[MAXN];
  48.  
  49. int main() {
  50. 	gi(N), gi(K);
  51.  
  52. 	int lo, hi;
  53. 	dq[lo=hi=0] = {{0, 0}, 0};
  54. 	int pref = 0;
  55. 	for (int i = 1, j = i-K; i <= N; i++, j++) {
  56. 		if (getc() == 'H') pref ++;
  57. 		else pref --;
  58.  
  59. 		auto val = dq[lo].first;
  60. 		if (val.second >= pref) val.first++;
  61. 		val.second = pref;
  62. 		while (lo <= hi && val <= dq[hi].first) --hi;
  63. 		dq[++hi] = {val, i};
  64.  
  65. 		if (dq[lo].second == j) lo++;
  66.  
  67. 		if (i == N) {
  68. 			cout << val.first << '\n';
  69. 		}
  70. 	}
  71.  
  72. 	return 0;
  73. }
  74.  
Success #stdin #stdout 0s 4404KB
comments (?)
stdin
copy 
7 2
HGHGGHG
stdout
copy 
3
https://ideone.com/nOJmA0
language:
C++14 (gcc 8.3)
created:
4 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!