fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. void solve() {
  8.     int n;
  9.     cin >> n;
  10.     vector<long long> h(n);
  11.     int M = 0;
  12.     for (int i = 0; i < n; ++i) {
  13.         cin >> h[i];
  14.         if (h[i] > h[M]) {
  15.             M = i;
  16.         }
  17.     }
  18.  
  19.     vector<long long> B(n - 1);
  20.     for (int i = 0; i < n - 1; ++i) {
  21.         B[i] = h[(M + 1 + i) % n];
  22.     }
  23.  
  24.     vector<long long> fL(n), fR(n);
  25.     vector<pair<long long, long long>> st;
  26.     long long current_sum = 0;
  27.  
  28.     fL[0] = 0;
  29.     for (int i = 1; i < n; ++i) {
  30.         long long x = B[i - 1];
  31.         long long cnt = 1;
  32.         while (!st.empty() && st.back().first <= x) {
  33.             current_sum -= st.back().first * st.back().second;
  34.             cnt += st.back().second;
  35.             st.pop_back();
  36.         }
  37.         st.push_back({x, cnt});
  38.         current_sum += x * cnt;
  39.         fL[i] = current_sum;
  40.     }
  41.  
  42.     st.clear();
  43.     current_sum = 0;
  44.     fR[n - 1] = 0;
  45.     for (int i = n - 2; i >= 0; --i) {
  46.         long long x = B[i];
  47.         long long cnt = 1;
  48.         while (!st.empty() && st.back().first <= x) {
  49.             current_sum -= st.back().first * st.back().second;
  50.             cnt += st.back().second;
  51.             st.pop_back();
  52.         }
  53.         st.push_back({x, cnt});
  54.         current_sum += x * cnt;
  55.         fR[i] = current_sum;
  56.     }
  57.  
  58.     vector<long long> ans(n);
  59.     for (int i = 0; i < n; ++i) {
  60.         ans[(M + 1 + i) % n] = fL[i] + fR[i];
  61.     }
  62.  
  63.     for (int i = 0; i < n; ++i) {
  64.         cout << ans[i] << (i == n - 1 ? "" : " ");
  65.     }
  66.     cout << "\n";
  67. }
  68.  
  69. int main() {
  70.     ios_base::sync_with_stdio(false);
  71.     cin.tie(NULL);
  72.     int t;
  73.     if (cin >> t) {
  74.         while (t--) {
  75.             solve();
  76.         }
  77.     }
  78.     return 0;
  79. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
4
4
1 2 3 4
5
5 3 1 5 2
6
3 4 2 6 1 5
7
1 2 1 4 2 3 5
stdout
copy 
6 6 7 9
17 16 14 14 17
21 21 20 20 21 21
17 17 17 17 21 21 22
https://ideone.com/egL4IU
language:
C++14 (gcc 8.3)
created:
1 day 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!