fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #ifdef LOCAL
  5. #include "cp/debug.h"
  6. #else
  7. #define debug(...)
  8. #endif
  9.  
  10. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  11.  
  12. const int MOD = (int) 1e9 + 7;
  13. const int INF = 0x3f3f3f3f;
  14.  
  15. struct ODT {
  16. 	map<int, int> tree;
  17. 	using It = map<int, int>::iterator;
  18.  
  19. 	It split(int x) {
  20. 		It it = tree.upper_bound(x);
  21. 		assert(it != tree.begin());
  22. 		it--;
  23. 		if (it->first == x) return it;
  24. 		return tree.emplace(x, it->second).first;
  25. 	}
  26.  
  27. 	pair<It, It> split(int l, int r) {
  28. 		return {split(l), split(r + 1)};
  29. 	}
  30.  
  31. 	void assign(int l, int r, int v) {
  32. 		auto [it_l, it_r] = split(l, r);
  33. 		while (it_l != it_r) {
  34. 			tree.erase(it_l++);
  35. 		}
  36. 		tree[l] = v;
  37. 	}
  38.  
  39. 	void reverse(int l, int r) {
  40. 		auto [it_l, it_r] = split(l, r);
  41. 		while (it_l != it_r) {
  42. 			it_l->second = !it_l->second;
  43. 			it_l++;
  44. 		}
  45. 	}
  46.  
  47. 	int count_one(int l, int r) {
  48. 		auto [it_l, it_r] = split(l, r);
  49. 		int ones = 0;
  50. 		while (it_l != it_r) {
  51. 			It prev = it_l++;
  52. 			ones += prev->second * (it_l->first - prev->first);
  53. 		}
  54. 		return ones;
  55. 	}
  56.  
  57. 	int longest_sequence(int l, int r) {
  58. 		auto [it_l, it_r] = split(l, r);
  59. 		int res = 0, cur = 0;
  60. 		while (it_l != it_r) {
  61. 			It prev = it_l++;
  62. 			if (prev->second == 0) cur = 0;
  63. 			else cur += it_l->first - prev->first;
  64. 			res = max(res, cur);
  65. 		}
  66. 		return res;
  67. 	}
  68. };
  69.  
  70. int main() {
  71. 	ios::sync_with_stdio(false); cin.tie(nullptr);
  72. 	int n, q;
  73. 	cin >> n >> q;
  74. 	vector<int> arr(n);
  75. 	ODT odt_tree;
  76. 	for (int i = 0; i < n; ++i) {
  77. 		cin >> arr[i];
  78. 		odt_tree.tree[i] = arr[i];
  79. 	}
  80. 	odt_tree.tree[n] = -1;
  81. 	for (int w = 0; w < q; ++w) {
  82. 		int type, l, r;
  83. 		cin >> type >> l >> r;
  84. 		if (type == 0 || type == 1) {
  85. 			odt_tree.assign(l, r, type);
  86. 		}
  87. 		else if (type == 2) {
  88. 			odt_tree.reverse(l, r);
  89. 		}
  90. 		else if (type == 3) {
  91. 			cout << odt_tree.count_one(l, r) << '\n';
  92. 		} else if (type == 4) {
  93. 			cout << odt_tree.longest_sequence(l, r) << '\n';
  94. 		} else {
  95. 			assert(false);
  96. 		}
  97. 	}
  98. 	return 0;
  99. }
  100.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
10 10
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9
stdout
copy 
5
2
6
5
https://ideone.com/JlgXbC
ODT
Chung kết CICTCPC 2023 - Phép toán trên dãy số
Problem link: https://d...content-available-to-author-only...u.vn/problem/sequenceops
language:
C++14 (gcc 8.3)
created:
6 days 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!