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
comments (?)
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
https://ideone.com/aRj0ti
language:
C++14 (gcc 8.3)
created:
8 years 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!