fork download
copy 
  1. /*
  2. 	www.youtube.com/YugiHackerChannel
  3. 	oj.vnoi.info/user/YugiHackerKhongCopCode
  4. */
  5. #include<bits/stdc++.h>
  6. #define el cout<<"\n"
  7. #define f0(i,n) for(int i=0;i<n;++i)
  8. #define f1(i,n) for(int i=1;i<=n;++i)
  9. #define maxn 500005
  10. #define MOD 1000000000
  11. using namespace std;
  12.  
  13. int n;
  14. long long a[maxn];
  15. long long ans;
  16. long long smin[maxn], smax[maxn], smm[maxn];
  17. long long gmin[maxn], gmax[maxn], gmm[maxn];
  18.  
  19. long long val(long long l, long long r)
  20. {
  21.     return (l + r) * (r - l + 1) / 2 % MOD;
  22. }
  23.  
  24. void solve(int l, int r)
  25. {
  26.     if (l == r)
  27.     {
  28.         (ans += a[l] * a[l]) %= MOD;
  29.         return;
  30.     }
  31.     int mid = (l+r)/2;
  32.  
  33.     solve(l, mid);
  34.     solve(mid + 1, r);
  35.  
  36.     long long ma = 0, mi = 1e9;
  37.     smin[mid] = smax[mid] = smm[mid] = gmin[mid] = gmax[mid] = gmm[mid] = 0;
  38.  
  39.     for (int i=mid+1; i<=r; ++i)
  40.     {
  41.         ma = max(ma, a[i]), mi = min(mi, a[i]);
  42.         smin[i] = (smin[i-1] + mi) % MOD;
  43.         smax[i] = (smax[i-1] + ma) % MOD;
  44.         smm[i] = (smm[i-1] + mi * ma) % MOD;
  45.         gmin[i] = (gmin[i-1] + mi) % MOD;
  46.         gmax[i] = (gmax[i-1] + ma) % MOD;
  47.         gmm[i] = (gmm[i-1] + mi * ma % MOD) % MOD;
  48.     }
  49.  
  50.     ma = 0, mi = 1e9;
  51.     int imin = mid, imax = mid;
  52.     for (int i=mid; i >= l; i--)
  53.     {
  54.         ma = max(ma, a[i]), mi = min(mi, a[i]);
  55.         while (imin < r && a[imin+1] >= mi) imin++;
  56.         while (imax < r && a[imax+1] <= ma) imax++;
  57.  
  58.         int pmin = min(imin, imax);
  59.         int pmax = max(imin, imax);
  60.  
  61.         ans = (ans + mi * ma % MOD * val(mid+2-i, pmin-i+1)) % MOD;
  62.         ans = (ans + gmm[r] - gmm[pmax] - (smm[r] - smm[pmax]) % MOD) % MOD;
  63.         if (imin < imax)
  64.             ans = (ans + ma * (gmin[pmax] - gmin[pmin] - (smin[pmax] - smin[pmin]) % MOD)) % MOD;
  65.         else
  66.             ans = (ans + mi * (gmax[pmax] - gmax[pmin] - (smax[pmax] - smax[pmin]) % MOD)) % MOD;
  67.     }
  68. }
  69.  
  70. main()
  71. {
  72.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  73.     cin >> n;
  74.     f1 (i, n) cin >> a[i];
  75.     solve(1, n);
  76.     cout << (ans + MOD) % MOD;
  77. }
  78.  
Success #stdin #stdout 0.01s 15812KB
comments (?)
stdin
copy 
4
1 4 3 1
stdout
copy 
55
https://ideone.com/L9keEf
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!