fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. int main(){
  6.     ios::sync_with_stdio(false);
  7.     cin.tie(nullptr);
  8.     int T; 
  9.     if(!(cin>>T)) return 0;
  10.     while(T--){
  11.         int n; cin>>n;
  12.         vector<ll>a(n);
  13.         for(int i=0;i<n;i++) cin>>a[i];
  14.  
  15.         // tìm 1 chỉ số chứa giá trị lớn nhất (chọn first max)
  16.         int pos = 0;
  17.         for(int i=1;i<n;i++) if(a[i] > a[pos]) pos = i;
  18.  
  19.         // xoay vòng (b là dãy bắt đầu từ pos), keep map -> original index
  20.         vector<ll> b(n);
  21.         vector<int> idx(n);
  22.         for(int i=0;i<n;i++){
  23.             int p = (pos + i) % n;
  24.             b[i] = a[p];
  25.             idx[i] = p; // b[i] corresponds to original index p
  26.         }
  27.  
  28.         // Build max-Cartesian tree on linear array b[0..n-1]
  29.         vector<int> parent(n, -1);
  30.         vector<int> st;
  31.         for(int i=0;i<n;i++){
  32.             int last = -1;
  33.             // use <= to break ties consistently (equal values handled)
  34.             while(!st.empty() && b[st.back()] <= b[i]){
  35.                 last = st.back();
  36.                 st.pop_back();
  37.             }
  38.             if(!st.empty()) parent[i] = st.back();     // nearest greater on left
  39.             if(last != -1) parent[last] = i;           // last popped -> parent is i (nearest greater on right)
  40.             st.push_back(i);
  41.         }
  42.  
  43.         // count children
  44.         vector<int> child(n,0);
  45.         for(int i=0;i<n;i++){
  46.             if(parent[i] != -1) child[parent[i]]++;
  47.         }
  48.  
  49.         // compute contributions back to original ordering
  50.         vector<ll> contrib(n, 0);
  51.         for(int i=0;i<n;i++){
  52.             int orig = idx[i];
  53.             contrib[orig] = b[i] * 1ll * child[i];
  54.         }
  55.  
  56.         // print contributions (per phần tử, theo thứ tự ban đầu)
  57.         for(int i=0;i<n;i++){
  58.             if(i) cout << ' ';
  59.             cout << contrib[i];
  60.         }
  61.         cout << '\n';
  62.     }
  63.     return 0;
  64. }
  65.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
3
4
1 1 3 2
2
0 2
7
1 1 4 5 1 4 1
stdout
copy 
0 1 3 2
0 2
1 1 4 5 0 8 0
https://ideone.com/ATG3OB
language:
C++ (gcc 8.3)
created:
8 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!