fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <chrono>
  3.  
  4. using namespace std;
  5. #define MAX 500
  6.   #define mod 1000000007
  7.  
  8. vector<vector<int>> lookup;
  9.  
  10. void buildSparseTable(int arr[], int n)
  11. {
  12.     for (int i = 0; i < n; i++)
  13.         lookup[i][0] = arr[i];
  14.  
  15.     for (int j = 1; (1 << j) <= n; j++) {
  16.  
  17.  
  18.         for (int i = 0; (i + (1 << j) - 1) < n; i++) {
  19.  
  20.  
  21.             if (lookup[i][j - 1] > lookup[i + (1 << (j - 1))][j - 1])
  22.                 lookup[i][j] = lookup[i][j - 1];
  23.             else
  24.                 lookup[i][j] = lookup[i + (1 << (j - 1))][j - 1];
  25.         }
  26.     }
  27. }
  28.  
  29.  
  30. int query(int L, int R)
  31. {
  32.  
  33.     int j = (int)log2(R - L + 1);
  34.  
  35.  
  36.     if (lookup[L][j] >= lookup[R - (1 << j) + 1][j])
  37.         return lookup[L][j];
  38.  
  39.     else
  40.         return lookup[R - (1 << j) + 1][j];
  41. }
  42.  
  43. // Driver program
  44. int main()
  45. {      
  46.    #ifndef ONLINE_JUDGE 
  47.    freopen("input.txt", "r", stdin); 
  48.    freopen("output.txt", "w", stdout); 
  49.    #endif  
  50.    auto start = chrono::high_resolution_clock::now();
  51.     int n; cin>>n;
  52.     int a[n];
  53.     // cout<<n<<'\n'; return 0;
  54.     for(int i=0;i<n;i++){
  55.         cin>>a[i];
  56.     }
  57.     int lg=log2(n);
  58.     lookup.resize(n);
  59.     for(int i=0;i<n;i++){
  60.         lookup[i].resize(lg);
  61.     }
  62.  
  63.     buildSparseTable(a, n);
  64.     int ans=0;
  65.     for(int k=1;k<=n;k++){
  66.         int l=0,r=k-1;
  67.         while(r<n){
  68.  
  69.             ans=(ans+(query(l,r)*k)%mod)%mod;
  70.             l++; r++;
  71.         }
  72.     }
  73.     cout<<ans<<'\n';
  74.     auto end = chrono::high_resolution_clock::now();
  75.   double time_taken = 
  76.       chrono::duration_cast<chrono::nanoseconds>(end - start).count();
  77.  
  78.     time_taken *= 1e-9;
  79.  
  80.     cout << "Time taken by program is : " << fixed 
  81.          << time_taken << setprecision(9);
  82.     cout << " sec" << endl;
  83.     return 0;
  84. }
  85.  
Success #stdin #stdout 0s 5412KB
comments (?)
stdin
copy 
3
2 3 1
stdout
copy 
27
Time taken by program is : 0.000041 sec
https://ideone.com/aIOOop
language:
C++ (gcc 8.3)
created:
2 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!