fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define TIME (1.0* clock()/CLOCKS_PER_SEC)
  3. #define pb push_back
  4. #define eb emplace_back
  5. #define id1 (id<<1)
  6. #define id2 (id<<1)|1
  7. #define ll long long
  8. #define ii pair<int,int>
  9. #define vi vector<int>
  10. #define vii vector<pair<int,int>> 
  11. #define vl vector<long long>
  12. #define vll vector <pair<ll,ll>>
  13. #define li pair<long long,int>
  14. #define vil vector <pair<int,ll>>
  15. #define db double
  16. #define ff first
  17. #define ss second
  18. #define lb lower_bound
  19. #define ub upper_bound
  20. #define FOR(i, a, b) for (int i = (a); i <=(b); i++)
  21. #define F0R(i, a) FOR(i, 0, a-1)
  22. #define ROF(i, a, b) for (int i = (b); i >= (a); i--)
  23. #define R0F(i, a) ROF(i, 0, a-1)
  24. #define rep(a) F0R(_, a)
  25. #define each(a, x) for (auto &a : x)
  26. #define ALL(x) (x).begin(),(x).end()
  27. #define pq priority_queue <li, vector <li>, greater <li>> 
  28. using namespace std;
  29. const int maxn=1e6;
  30. //const int MOD=1e9+7;
  31. //const int MOD=998244353;
  32. //const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};
  33. int n;
  34.  
  35. void solve(){
  36.     cin >> n;
  37.     vl a(n);
  38.     for(int i=0;i<n;i++) cin>>a[i];
  39.  
  40.  
  41.     int pos=0;
  42.     for(int i=1;i<n;i++) {
  43.         if(a[i] > a[pos]) pos = i;
  44. 	}
  45.  
  46.     vl b(n);
  47.     for(int i = 0; i < n; i++){
  48.         b[i] = a[(pos + i) % n];
  49. 	}
  50.     vi parent(n, -1), st;
  51.     for(int i = 0; i < n; i++){
  52.         int last = -1;
  53.         while(!st.empty() && b[st.back()] <= b[i]){
  54.             last = st.back();
  55.             st.pop_back();
  56.         }
  57.         if(!st.empty()) parent[i] = st.back();
  58.         if(last != -1) parent[last] = i;
  59.         st.push_back(i);
  60.     }
  61.  
  62.  
  63.     vi child(n, 0);
  64.     for(int i = 0; i < n; i++)
  65.         if(parent[i] != -1) child[parent[i]]++;
  66.  
  67.  
  68.     ll ans = 0;
  69.     for(int i = 0; i < n; i++)
  70.         ans += b[i] * 1LL * child[i];
  71.  
  72.     cout << ans << "\n";
  73. }
  74.  
  75. signed main(){
  76.   ios_base::sync_with_stdio(false);
  77.   cin.tie(NULL);cout.tie(NULL);
  78.   if (fopen("TASK.INP", "r")){
  79.       freopen("TASK.INP", "r", stdin);
  80.       freopen("TASK.OUT", "w", stdout);
  81.   }
  82.   int ntest;
  83.   ntest=1;
  84.   cin>>ntest;
  85.  
  86.   for(int i=1;i<=ntest;i++) solve();
  87.   cerr<<"\n"<<"Time elapsed "<<TIME<<"s.\n";
  88.   return 0;
  89. }
Success #stdin #stdout #stderr 0s 5320KB
comments (?)
stdin
copy 
3
4
1 1 3 2
2
0 2
7
1 1 4 5 1 4 1
stdout
copy 
6
2
19
stderr
copy 
Time elapsed 0.004694s.
https://ideone.com/VXhNEo
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!