fork(1) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. int equality(int a, int b){
  6. 	return a == b ? a : 0;
  7. }
  8.  
  9. void build(int *a, int *tr, int v, int l, int r) {
  10. 	if (l == r) {
  11. 		tr[v] = a[l];
  12. 	} else {
  13. 		int middle = (l + r) / 2;
  14. 		build(a, tr, 2 * v, l, middle);
  15. 		build(a, tr, 2 * v + 1, middle + 1, r);
  16. 		tr[v] = equality(tr[2 * v], tr[2 * v + 1]);
  17. 	}
  18. }
  19.  
  20. void update(int *tr, int v, int l, int r, int pos, int val) {
  21. 	if (l == r) {
  22. 		tr[v] = val;
  23. 	} else {
  24. 		int middle = (l + r) / 2;
  25. 		if (pos <= middle) {
  26. 			update(tr, 2 * v, l, middle, pos, val);
  27. 		} else {
  28. 			update(tr, 2 * v + 1, middle + 1, r, pos, val);
  29. 		}
  30. 		tr[v] = equality(tr[2 * v], tr[2 * v + 1]);
  31. 	}
  32. }
  33.  
  34. int getEquality(int *tr, int v, int l, int r, int left, int right) {
  35. 	if (l == left && r == right) {
  36. 		return tr[v];
  37. 	}
  38. 	int middle = (l + r) / 2;
  39. 	if (right <= middle) {
  40. 		return getEquality(tr, 2 * v, l, middle, left, right);
  41. 	}
  42. 	else if (left >= middle + 1) {
  43. 		return getEquality(tr, 2 * v + 1, middle + 1, r, left, right);
  44. 	}
  45. 	else {
  46. 		return equality(getEquality(tr, 2 * v, l, middle, left, middle), 
  47. 			getEquality(tr, 2 * v + 1, middle + 1, r, middle + 1, right));
  48. 	}
  49. }
  50.  
  51. int main() {
  52. 	int n;
  53. 	cin >> n;
  54. 	int *a = new int[n];
  55. 	for (int i = 0; i < n; i++) {
  56. 		cin >> a[i];
  57. 	}
  58. 	int *tr = new int[4 * n];
  59. 	build(a, tr, 1, 0, n - 1);
  60. 	int m;
  61. 	cin >> m;
  62. 	for (int i = 0; i < m; i++) {
  63. 		int q, l, r;
  64. 		cin >> q >> l >> r;
  65. 		if (q == 1) {
  66. 			cout << (getEquality(tr, 1, 0, n - 1, l - 1, r - 1) != 0 ? "draw" : "wins") << endl;
  67. 		} else if (q == 2) {
  68. 			update(tr, 1, 0, n - 1, l - 1, r);
  69. 		}
  70. 	}
  71. 	return 0;
  72. }
Time limit exceeded #stdin #stdout 5s 3456KB
comments (?)
stdin
copy 
3
4 8 11
3
2 1 7
2 2 10
1 1 4
stdout
copy 
Standard output is empty
https://ideone.com/AGnFbC
4482
language:
C++14 (gcc 8.3)
created:
7 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!