fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define Task "MinMax"
  5. #define sp " "
  6. #define endl "\n"
  7. #define int long long
  8. #define sz(x) (int)x.size()
  9.  
  10. constexpr int maxn = 2e5 + 5;
  11.  
  12. int n, cnt = 0;
  13. int a[maxn], b[maxn];
  14.  
  15. int f[maxn][20];
  16. int g[maxn][20];
  17.  
  18. void Preprocess() {
  19.     for(int i = 1; i <= 17; i++) {
  20.         for(int u = 1; u <= n - (1 << (i - 1)) + 1; u++) {
  21.             f[u][i] = min(f[u][i - 1], f[u + (1 << (i - 1))][i - 1]);
  22.             g[u][i] = max(g[u][i - 1], g[u + (1 << (i - 1))][i - 1]);
  23.         }
  24.     }
  25. }
  26.  
  27. int GetMax(int l, int r) {
  28.     int k = log2(r - l + 1);
  29.     return max(g[l][k], g[r - (1 << k) + 1][k]);
  30. }
  31.  
  32. int GetMin(int l, int r) {
  33.     int k = log2(r - l + 1);
  34.     return min(f[l][k], f[r - (1 << k) + 1][k]);
  35. }
  36.  
  37. signed main() {
  38.     ios_base::sync_with_stdio(false);
  39.     cin.tie(nullptr);
  40.  
  41.     if(fopen(Task".inp", "r")) {
  42.         freopen(Task".inp", "r", stdin);
  43.         freopen(Task".out", "w", stdout);
  44.     }
  45.  
  46.     cin >> n;
  47.  
  48.     for(int i = 1; i <= n; i++) {
  49.         cin >> a[i];
  50.         g[i][0] = a[i];
  51.     }
  52.  
  53.     for(int i = 1; i <= n; i++) {
  54.         cin >> b[i];
  55.         f[i][0] = b[i];
  56.     }
  57.  
  58.     Preprocess();
  59.  
  60.     for(int l = 1; l <= n; l++) {
  61.         int r1 = -1, r2 = -1;
  62.  
  63.         int low = l, high = n;
  64.         while(low <= high) {
  65.             int mid = low + (high - low) / 2;
  66.             if(GetMax(l, mid) >= GetMin(l, mid)) {
  67.                 r1 = mid;
  68.                 high = mid - 1;
  69.             }
  70.             else {
  71.                 low = mid + 1;
  72.             }
  73.         }
  74.  
  75.         low = l, high = n;
  76.         while(low <= high) {
  77.             int mid = low + (high - low) / 2;
  78.             if(GetMax(l, mid) > GetMin(l, mid)) {
  79.                 r2 = mid;
  80.                 high = mid - 1;
  81.             }
  82.             else {
  83.                 low = mid + 1;
  84.             }
  85.         }
  86.  
  87.         if(r1 != -1) {
  88.             if(GetMax(l, r1) == GetMin(l, r1)) {
  89.                 if (r2 == -1) {
  90.                     cnt += (n - r1 + 1);
  91.                 }
  92.                 else {
  93.                     cnt += (r2 - r1);
  94.                 }
  95.             }
  96.         }
  97.     }
  98.  
  99.     cout << cnt << endl;
  100.  
  101.     return 0;
  102. }
  103.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/R0vekI
language:
C++14 (gcc 8.3)
created:
14 hours 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!