fork(1) download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int INF = 1e+9 + 17;
  6.  
  7. struct Segment_Tree
  8. {
  9. vector <int> a, b;
  10. vector <pair <int, int> > T;
  11.  
  12. int sz;
  13. pair <int, int> ans;
  14.  
  15. Segment_Tree(vector <int> &x, vector <int> &y)
  16. {
  17. sz = x.size();
  18. a = x;
  19. b = y;
  20. T.resize((sz << 2), {INF, -INF});
  21. build(1, 0, sz - 1);
  22. }
  23.  
  24. void build (int v, int l, int r)
  25. {
  26. if (l > r)
  27. return;
  28. if (l == r)
  29. {
  30. T[v] = {b[l], a[r]};
  31. return;
  32. }
  33.  
  34. int m = (l + r) >> 1;
  35.  
  36. build(2*v, l, m);
  37. build(2*v + 1, m + 1, r);
  38.  
  39. T[v].first = min(T[2*v].first, T[2*v + 1].first);
  40. T[v].second = max(T[2*v].second, T[2*v + 1].second);
  41. }
  42.  
  43. void get_ans(int v, int L, int R, int l, int r)
  44. {
  45. if (L > R)
  46. return;
  47.  
  48. if (l > r)
  49. return;
  50.  
  51. if (L == l && r == R)
  52. {
  53. ans.first = min(ans.first, T[v].first), ans.second = max(ans.second, T[v].second);
  54. return;
  55. }
  56. int m = (L + R) >> 1;
  57.  
  58. get_ans(2*v, L, m, l, min(r, m));
  59. get_ans(2*v + 1, m + 1, R, max(l, m + 1), r);
  60. }
  61.  
  62. int get_ans(int l, int r) {
  63. ans = {INF, -INF};
  64.  
  65. get_ans(1, 0, sz - 1, l, r);
  66.  
  67. return ans.second - ans.first;
  68. }
  69. };
  70.  
  71. int main()
  72. {
  73. ios_base::sync_with_stdio(false);
  74. cin.tie(nullptr);
  75.  
  76. int n;
  77. long long ANS = 0;
  78. cin >> n;
  79.  
  80. vector <int> a(n);
  81. vector <int> b(n);
  82.  
  83. for (int i = 0; i < n; i++) cin >> a[i];
  84. for (int i = 0; i < n; i++) cin >> b[i];
  85.  
  86. Segment_Tree t = Segment_Tree(a, b);
  87.  
  88. for (int l = 0; l < n; l++)
  89. {
  90. int L = l - 1, R = n - 1;
  91.  
  92. while (R - L > 1)
  93. {
  94. int m = (L + R) >> 1;
  95. if (t.get_ans(l, m) >= 0)
  96. R = m;
  97. else
  98. L = m;
  99. }
  100.  
  101. if (t.get_ans(l, R) == 0)
  102. {
  103. int l1 = R - 1, r1 = n;
  104. while (r1 - l1 > 1)
  105. {
  106. int m = (l1 + r1) >> 1;
  107. if (t.get_ans(l, m))
  108. r1 = m;
  109. else
  110. l1 = m;
  111. }
  112. ANS += r1 - R;
  113. }
  114. }
  115.  
  116. cout << ANS << endl;
  117. }
  118.  
Runtime error #stdin #stdout #stderr 0s 3468KB
stdin
Standard input is empty
stdout
Standard output is empty
stderr
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc