fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5.  
  6. const int MAXN = 1000005;
  7. const int LOG = 20;
  8.  
  9. int st[LOG][MAXN];
  10.  
  11. int main() {
  12.     int n;
  13.     if (!(cin >> n)) return 0;
  14.  
  15.     for (int i = 0; i < n; ++i)
  16.         cin >> st[0][i];
  17.  
  18.     for (int j = 1; (1 << j) <= n; ++j)
  19.         for (int i = 0; i + (1 << j) <= n; ++i)
  20.             st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
  21.  
  22.     int m;
  23.     cin >> m;
  24.  
  25.     long long total_sum = 0;
  26.  
  27.     while(m--) {
  28.         int L, R;
  29.         cin >> L >> R;
  30.  
  31.         int len = R - L + 1;
  32.         int log_len = 31 - __builtin_clz(len);
  33.         int current_min = min(st[log_len][L], st[log_len][R - (1 << log_len) + 1]);
  34.  
  35.         total_sum += current_min;
  36.     }
  37.  
  38.     cout << total_sum << "\n";
  39.  
  40.     return 0;
  41. }
  42.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/d76e20
language:
C++14 (gcc 8.3)
created:
2 days 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!