fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #include <iostream>
  4. #define Sa7afy22 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  5. #define Time cerr << "Time Taken: " << (float)clock() / CLOCKS_PER_SEC << " Secs" << "\n";
  6. #define cin(v) for (auto&i:v) cin >> i;
  7. #define cout(v) for (auto&i:v) cout << i << " ";cout<<e;
  8. #include <algorithm>
  9. #include <vector>
  10. #define ll long long int
  11. #define e '\n'
  12. #define PI acos(-1)
  13. #define PHI (long double)1.61803398875 //golden ratio
  14. #define sin(a) sin((a)*PI/180)
  15. #define cos(a) cos((a)*PI/180)
  16. #define tan(a) tan((a)*PI/180)
  17. #define  eb emplace_back
  18. #define ones(x) __builtin_popcountll(x)
  19. #define all(v) v.begin(), v.end()
  20. #define allr(v) v.rbegin(), v.rend()
  21. #define pii pair<ll,ll>
  22. #define vi vector<int>
  23. #define vll vector<ll>
  24. #include <set>
  25. #include <deque>
  26. #define d2v vector<vector<int>>
  27. typedef pair<int,int> Pii;
  28. #define  pb push_back
  29.  
  30. const int mod = 1e9+7;
  31.  
  32. ll mult(ll a, ll b){ return ((a % mod) * (b % mod)) % mod; }
  33. ll add(ll a, ll b) { return ((a % mod) + (b % mod)) % mod; }
  34. ll sub(ll a, ll b) { return ((a % mod) - (b % mod) + mod) % mod; }
  35. int dx[]={1,0,-1,0,1,1,-1,-1};
  36. int dy[]={0,1,0,-1,1,-1,-1,1};
  37.  
  38. const int N = 1e5+5;
  39.  
  40.  
  41.  
  42. struct BIT{
  43.     vector<ll>tree;
  44.     BIT(int sz) {
  45.         tree.resize(sz + 1);
  46.     }
  47.     ll get(int x) {
  48.         ll res = 0;
  49.         while (x>0) {
  50.             res = add(tree[x],res);
  51.             x -= x & -x;
  52.         }
  53.         return res;
  54.     }
  55.  
  56.     void update (ll x,ll val) {
  57.         while (x < tree.size()) {
  58.             tree[x] = add(tree[x],val);
  59.             x += x & -x;
  60.         }
  61.     }
  62.  
  63.     ll query(int l,int r) {
  64.         if (r < l)return 0;
  65.         return get(r) - get(l - 1);
  66.     }
  67. };
  68. void solve () {
  69.     int n;
  70.     cin >> n;
  71.     vector<ll> arr(n);
  72.     for (int i = 0; i < n; i++) {
  73.         cin >> arr[i];
  74.         if (i)arr[i] += arr[i - 1];
  75.     }
  76.     vector<ll> prefix(n);
  77.     for (int i = 0; i < n; i++) {
  78.         prefix[i] = arr[i];
  79.     }
  80.  
  81.     vector<ll> vals;
  82.     for (int i = 0; i < n; ++i) {
  83.         vals.push_back(arr[i]);
  84.     }
  85.     sort(all(vals));
  86.     vals.erase(unique(vals.begin(), vals.end()),
  87.                vals.end());
  88.     for (int i = 0; i < n; ++i) {
  89.         arr[i] = lower_bound(all(vals), arr[i]) -
  90.                  vals.begin() + 1;
  91.     }
  92.  
  93.     BIT Freqtree(n+ 1);
  94.     BIT Sumtree(n + 1);
  95.     ll ans{};
  96.     for (int i = 0; i < n; i++) {
  97.         if (prefix[i] > 0)
  98.             ans = add(prefix[i], ans);
  99.         ll freq = Freqtree.query(1, arr[i] - 1), sum = Sumtree.query(1, arr[i] - 1);
  100.         ans = add(ans, sub(mult(freq, prefix[i]), sum));
  101.         Sumtree.update(arr[i], prefix[i]);
  102.         Freqtree.update(arr[i], 1);
  103.     }
  104.     cout << ans << '\n';
  105. }
  106.  
  107. signed main() {
  108.     Sa7afy22
  109. #ifndef ONLINE_JUDGE
  110.     freopen("testcase.txt", "r", stdin);
  111.     freopen("output.txt", "w", stdout);
  112. #endif
  113.     int tests = 1;
  114.     //cin >> tests;
  115.     for (int i = 1; i <= tests; i++) {
  116.         /*cout<<"Case #"<<i<<": ";*/
  117.         solve();
  118.     }
  119.     Time
  120. }
Success #stdin #stdout #stderr 0.28s 40340KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Error: unexpected symbol in "using namespace"
Execution halted
https://ideone.com/5Lf4Hh
language:
R (R 3.5.2)
created:
28 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!