Advertisement
lalalalalalalaalalla

Untitled

Dec 15th, 2019
137
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.76 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <iomanip>
  5. #include <queue>
  6. #include <cmath>
  7. #include <algorithm>
  8. #include <tuple>
  9. #include <iomanip>
  10. #include <stdio.h>
  11. #include <numeric>
  12. #include <map>
  13. #include <bitset>
  14. #include <set>
  15. #include <stack>
  16. #include <queue>
  17.  
  18. /*
  19. #pragma GCC optimize("Ofast,no-stack-protector")
  20. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
  21. #pragma GCC optimize("unroll-loops")
  22. #pragma GCC optimize("fast-math")
  23. #pragma GCC optimize("section-anchors")
  24. #pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
  25. #pragma GCC optimize("vpt")
  26. #pragma GCC optimize("rename-registers")
  27. #pragma GCC optimize("move-loop-invariants")
  28. #pragma GCC optimize("unswitch-loops")
  29. #pragma GCC optimize("function-sections")
  30. #pragma GCC optimize("data-sections")
  31. #pragma GCC optimize("branch-target-load-optimize")
  32. #pragma GCC optimize("branch-target-load-optimize2")
  33. #pragma GCC optimize("btr-bb-exclusive")
  34. */
  35.  
  36. #define int long long
  37. #define ll long long
  38. #define ull unsigned long long
  39. #define all(a) a.begin(), a.end()
  40. #define pii pair<int, int>
  41. #define pb push_back
  42. #define ld long double
  43.  
  44.  
  45. using namespace std;
  46.  
  47. const int INF = 1e13;
  48. //const int mod = 2600000069;
  49. //const int p = 179;
  50.  
  51. struct wat{
  52. int open, close, ans;
  53. wat(int max_, int left_, int right_) {
  54. ans = max_;
  55. open = left_;
  56. close = right_;
  57. }
  58. wat() {
  59. ans = 0;
  60. close = 0;
  61. open = 0;
  62. }
  63. };
  64.  
  65. vector<wat> t;
  66. string s;
  67.  
  68. wat merge(wat a, wat b) {
  69. wat c;
  70. int q = min(a.open, b.close);
  71. c.ans = a.ans + b.ans + 2 * q;
  72. c.open = a.open + b.open - q;
  73. c.close = a.close + b.close - q;
  74. return c;
  75. }
  76.  
  77. void build(int v, int l, int r) {
  78. if (r - l == 1) {
  79. t[v] = wat(0, (s[l] == '(' ? 1 : 0), (s[l] == ')' ? 1 : 0));
  80. return;
  81. }
  82. int m = (l + r) / 2;
  83. build(2 * v + 1, l, m);
  84. build(2 * v + 2, m, r);
  85. t[v] = merge(t[2 * v + 1], t[2 * v + 2]);
  86. }
  87.  
  88. wat get_ans(int v, int l, int r, int askl, int askr) {
  89. if (l >= askr || r <= askl) {
  90. return wat();
  91. }
  92. if (l >= askl && r <= askr) {
  93. return t[v];
  94. }
  95. int m = (l + r) / 2;
  96. return merge(get_ans(2 * v + 1, l, m, askl, askr), get_ans(2 * v + 2, m, r, askl, askr));
  97. }
  98.  
  99. signed main() {
  100. ios_base::sync_with_stdio(0);
  101. cin.tie(0);
  102. cout.tie(0);
  103. cin >> s;
  104. int n = s.size();
  105. t.resize(4 * n);
  106. build(0, 0, n);
  107. int m;
  108. cin >> m;
  109. int l, r;
  110. while (m--) {
  111. cin >> l >> r;
  112. l--;
  113. cout << get_ans(0, 0, n, l, r).ans << "\n";
  114. }
  115. }
  116. /*
  117. ())(())(())(
  118. 7
  119. 1 1
  120. 2 3
  121. 1 2
  122. 1 12
  123. 8 12
  124. 5 11
  125. 2 10
  126. ->
  127. 0
  128. 0
  129. 2
  130. 10
  131. 4
  132. 6
  133. 6
  134. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement