fork download
copy 
  1. /*
  2. *  <|--- <<_||_>> ---|>
  3. *  <---  >>-\\-<<  --->
  4. *  <|--- <<_||_>> ---|>
  5. */
  6. // problem 1 --> Balanced Intervals
  7. #include <bits/stdc++.h>
  8. #include <ext/pb_ds/assoc_container.hpp>
  9. #include <ext/pb_ds/tree_policy.hpp>
  10.  
  11. using namespace std;
  12. using namespace __gnu_pbds;
  13.  
  14. typedef tree<int, null_type, less<int>, rb_tree_tag,
  15.     tree_order_statistics_node_update> ordered_set;
  16.  
  17. #define el     '\n'
  18. #define int long long
  19. const int mod = 1000000000 + 7;
  20.  
  21. void solve() {
  22.     int n;
  23.     cin >> n;
  24.  
  25.     vector<int> a(n + 1);
  26.     vector<vector<int> > pos(n + 1);
  27.     set<int> bad;
  28.  
  29.     bad.insert(0);
  30.     bad.insert(n + 1);
  31.  
  32.     for (int i = 1; i <= n; ++i) {
  33.         cin >> a[i];
  34.         if (a[i] > n) {
  35.             bad.insert(i);
  36.         } else {
  37.             pos[a[i]].push_back(i);
  38.         }
  39.     }
  40.  
  41.     int total_balanced = 0;
  42.     for (int v = n; v >= 1; --v) {
  43.         int k = pos[v].size();
  44.  
  45.         for (int j = 0; j <= k - v; ++j) {
  46.             int L_pos = pos[v][j];
  47.             int R_pos = pos[v][j + v - 1];
  48.             auto it = bad.upper_bound(L_pos);
  49.             int B_next = *it;
  50.  
  51.             if (B_next < R_pos) {
  52.                 continue;
  53.             }
  54.  
  55.             int B_L = *prev(it);
  56.             int B_R = B_next;
  57.             int prev_v_pos = (j > 0) ? pos[v][j - 1] : 0;
  58.             int next_v_pos = (j + v < k) ? pos[v][j + v] : n + 1;
  59.  
  60.             int limit_L = max(B_L, prev_v_pos);
  61.             int limit_R = min(B_R, next_v_pos);
  62.             total_balanced += 1LL * (L_pos - limit_L) * (limit_R - R_pos);
  63.         }
  64.  
  65.         for (int p: pos[v]) {
  66.             bad.insert(p);
  67.         }
  68.     }
  69.  
  70.     cout << total_balanced << el;
  71. }
  72.  
  73. int32_t main() {
  74.     ios_base::sync_with_stdio(false);
  75.     cout.tie(nullptr), cin.tie(nullptr);
  76.  
  77.     int tt = 1;
  78.     //cin >> tt;
  79.     while (tt--) {
  80.         solve();
  81.     }
  82.     return 0;
  83. }
  84.  
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/oSfxwy
language:
C++ (gcc 8.3)
created:
1 hour 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!