fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <iostream>
  3. #include <ext/pb_ds/assoc_container.hpp> 
  4. #include <ext/pb_ds/tree_policy.hpp>
  5.  
  6. using namespace std;
  7. using namespace __gnu_pbds;
  8.  
  9. typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> ost;
  10.  
  11. typedef long long ll;
  12.  
  13. const int MAXN = 1e5+5;
  14.  
  15. int n, psa[MAXN];
  16.  
  17. /*
  18. consider what happens in a operation
  19. 1: ai-1 += ai
  20. 2:ai+1 += ai
  21. 3: ai += -2ai
  22.  
  23. 2 1 0 5 7 5 14
  24.  
  25. if we build a psum we just check if its possible to sort it using some operations
  26. psa[1] must be non negative
  27.  
  28. operating on index i
  29. all things before dont matter
  30. psa[i-1] += a[i]
  31. psa[i] += -2a[i] + a[i] = -a[i]
  32. psa[i+1] += a[i] - a[i] = 0
  33. all things after dont get contribution
  34.  
  35. so in one operation:
  36. psa[i-1] += a[i] = psa[i] - psa[i-1]
  37. psa[i] += -a[i] = -(psa[i] - psa[i-1])
  38.  
  39. psa[i-1] = psa[i]
  40. psa[i] = psa[i-1]
  41.  
  42. so they just swap
  43. */
  44.  
  45. int main() {
  46.     cin >> n;
  47.  
  48.     for(int i = 1; i <= n; i++){
  49.         cin >> psa[i];
  50.         psa[i] += psa[i-1];
  51.     }
  52.  
  53.     for(int i = 1; i <= n; i++){
  54.         if(psa[i] < 0){
  55.             cout << "-1\n";
  56.             return 0;
  57.         }
  58.     }
  59.     ost t;
  60.     long long ans = 0;
  61.     for(int i = 1; i <= n; i++){
  62.         ans += i - t.order_of_key({psa[i], i}) - 1;
  63.         t.insert({psa[i], i});
  64.     }
  65.  
  66.     cout << ans << "\n";
  67. }
  68.  
  69.  
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
7
2 -1 -1 5 2 -2 9
stdout
copy 
4
https://ideone.com/fm2mZm
language:
C++14 (clang 8.0)
created:
15 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!