fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std; 
  3.  
  4. typedef long long ll; 
  5. typedef pair <int, int> ii; 
  6.  
  7. const ll LINF = 1e18; 
  8. const int INF = 1e9;
  9. const int N = 1e6 + 5; 
  10.  
  11. struct node {
  12. 	int ans = 0, rem_open = 0, rem_close = 0; 
  13.  
  14. 	node() {}
  15.  
  16. 	node(int ans, int rem_open, int rem_close): ans(ans), rem_open(rem_open), rem_close(rem_close) {}
  17.  
  18. 	node(char bracket) {
  19. 		if (bracket == '(') rem_open = 1;  
  20. 		if (bracket == ')') rem_close = 1; 
  21. 	}
  22.  
  23. 	node operator+(const node& other) {
  24. 		node sum;   
  25. 		int bonus = min(rem_open, other.rem_close); // số cặp ngoặc đúng có thêm 
  26. 		sum.ans = ans + other.ans + bonus; // số cặp ngoặc đúng sau khi gộp
  27. 		sum.rem_open = (rem_open - bonus) + other.rem_open; // số ngoặc mở còn thừa sau khi gộp                                                       
  28. 		sum.rem_close = rem_close + (other.rem_close - bonus); // số ngoặc đóng còn thừa sau khi gộp
  29. 		return sum; 
  30. 	}
  31. }; 
  32.  
  33. int n, m; 
  34. string s; 
  35. node seg[4 * N]; 
  36.  
  37. void build(int id, int l, int r) {
  38. 	if (l == r) {
  39. 		seg[id] = node(s[l]); 
  40. 		return; 
  41. 	}
  42.  
  43. 	int mid = (l + r) >> 1; 
  44. 	build(id * 2, l, mid); 
  45. 	build(id * 2 + 1, mid + 1, r); 
  46.  
  47. 	seg[id] = seg[id * 2] + seg[id * 2 + 1]; 
  48. }
  49.  
  50. node get(int id, int l, int r, int u, int v) {
  51. 	if (l > v || r < u) return node();
  52.  
  53. 	if (u <= l && r <= v) return seg[id]; 
  54.  
  55. 	int mid = (l + r) >> 1;  
  56.  
  57. 	return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v); 
  58. }
  59.  
  60. int main() {
  61. 	ios::sync_with_stdio(0); 
  62. 	cin.tie(0); 
  63. 	cin >> s >> m; 
  64. 	n = s.size();
  65.  
  66. 	build(1, 0, n - 1); 
  67.  
  68. 	for (int i = 0; i < m; i++) {
  69. 		int l, r; 
  70. 		cin >> l >> r; 
  71.  
  72. 		l--, r--; 
  73.  
  74. 		cout << get(1, 0, n - 1, l, r).ans * 2 << '\n'; 
  75. 	}
  76. }
Success #stdin #stdout 0.01s 50504KB
comments (?)
stdin 
())(())(())(
7
1 1
2 3
1 2
1 12
8 12
5 11
2 10
stdout 
0
0
2
10
4
6
6
https://ideone.com/NIhNtG
language:
C++14 (gcc 8.3)
created:
1 year 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!