fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. inline int read()
  8. {
  9. 	int x = 0; int v = 1, c;
  10. 	while(c = getchar(), c < '0' || c > '9') if(c == '-') v = -1;
  11. 	for(; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
  12. 	return x * v;
  13. }
  14.  
  15. const int maxn = 100005;
  16.  
  17. int n, tot, q;
  18. int col[maxn << 2], set[maxn << 2];
  19.  
  20. inline int calc(int x)
  21. {
  22. 	int res = 0;
  23. 	while(x) {
  24. 		x -= x & -x;
  25. 		res++;
  26. 	}
  27. 	return res;
  28. }
  29.  
  30. #define lc o << 1
  31. #define rc lc | 1
  32. #define Lc lc, L, M
  33. #define Rc rc, M + 1, R
  34.  
  35. inline void pushdown(int o)
  36. {
  37. 	if(set[o]) {
  38. 		set[lc] = set[rc] = col[lc] = col[rc] = set[o]; set[o] = 0;
  39. 	}
  40. }
  41.  
  42. inline void maintain(int o)
  43. {
  44. 	col[o] = col[lc] | col[rc];
  45. }
  46.  
  47. void color(int o, int L, int R, int ql, int qr, int c)
  48. {
  49. 	if(L == ql && qr == R) {
  50. 		set[o] = col[o] = c;
  51. 	} else {
  52. 		pushdown(o);
  53. 		int M = (L + R) >> 1;
  54. 		if(qr <= M) {
  55. 			color(Lc, ql, qr, c);
  56. 		} else if(M < ql) {
  57. 			color(Rc, ql, qr, c);
  58. 		} else {
  59. 			color(Lc, ql, M, c);
  60. 			color(Rc, M + 1, qr, c);
  61. 		}
  62. 		maintain(o);
  63. 	}
  64. }
  65.  
  66. int query(int o, int L, int R, int ql, int qr)
  67. {
  68. 	if(L == ql && qr == R) {
  69. 		return col[o];
  70. 	} else {
  71. 		pushdown(o);
  72. 		int M = (L + R) >> 1;
  73. 		if(qr <= M) {
  74. 			return query(Lc, ql, qr);
  75. 		} else if(M < ql) {
  76. 			return query(Rc, ql, qr);
  77. 		} else {
  78. 			return query(Lc, ql, M) | query(Rc, M + 1, qr);
  79. 		}
  80. 	}
  81.  
  82. }
  83.  
  84. int main()
  85. {
  86. #ifndef ONLINE_JUDGE
  87. 	freopen("input.txt", "r", stdin);
  88. 	freopen("output.txt", "w", stdout);
  89. #endif
  90.  
  91. 	register int a, b, c, ans;
  92. 	n = read(), tot = read(), q = read();
  93. 	memset(set, 0, sizeof(set)); set[1] = col[1] = 1;
  94. 	while(q--) {
  95. 		static char op[3];
  96. 		scanf("%s", op);
  97. 		a = read(), b = read();
  98. 		if(a > b) swap(a, b);
  99. 		if(op[0] == 'C') {
  100. 			c = read();
  101. 			color(1, 1, n, a, b, 1 << c - 1);
  102. 		} else {
  103. 			ans = query(1, 1, n, a, b);
  104. 			printf("%d\n", calc(ans));
  105. 		}
  106. 	}
  107.  
  108. #ifndef ONLINE_JUDGE
  109. 	fclose(stdin), fclose(stdout);
  110. #endif
  111. 	return 0;
  112. }
  113.  
Time limit exceeded #stdin #stdout 5s 6580KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/EUCx9s
poj2777
language:
C++14 (clang 8.0)
created:
9 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!