fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> orderedset;
  7. #define MO2 ios_base::sync_with_stdio(false);cin.tie(NULL);
  8. #define endl '\n'
  9. #define int long long
  10. #define elif else if
  11. #define sz(x) long(x.size())
  12. #define all(vec) vec.begin(), vec.end()
  13. const int mod = 1e9 + 7;
  14. const int dx[] = {0, -1, 0, 1, 1, -1, 1, -1};
  15. const int dy[] = {-1, 0, 1, 0, 1, 1, -1, -1};
  16.  
  17. int n, m;
  18. string s, z;
  19. vector<int> ind, val,vec;
  20. void dope() {}
  21. bool can (int mid) {
  22.     return val[mid] > m;
  23. }
  24. int BS() {
  25.     int l = 0, r = sz(ind) - 1, ans = sz(ind);
  26.     while (l <= r) {
  27.         int mid = (l + r) / 2;
  28.         if (can(mid)) {
  29.             r = mid - 1;
  30.             ans = mid;
  31.         }
  32.         else
  33.             l = mid + 1;
  34.     }
  35.     return sz(ind) - ans;
  36. }
  37. void solve() {
  38.     cin >> n;
  39.     vec = vector<int>(n);
  40.     set<pair<int, int>> st;
  41.     for (int i = 0; i < n; i++) {
  42.         cin >> vec[i];
  43.         if (vec[i] < i + 1)
  44.             st.insert({i + 1, vec[i]});
  45.     }
  46.     int ans = 0;
  47.     ind = val = vector <int> (0);
  48.     for (auto&it:st)
  49.         ind.push_back(it.first), val.push_back(it.second);
  50.  
  51.     for (int i = 0; i < sz(ind); i++) {
  52.         m = ind[i];
  53.         ans += BS();
  54.     }
  55.     cout << ans;
  56. }
  57. signed main() {
  58.     MO2
  59. #if ONLINE_JUDGE || CPH
  60. #else
  61.     freopen("Input.txt", "r", stdin);
  62.     freopen("Output.txt", "w", stdout);
  63. #endif
  64.     int nop = 1;  cin >> nop;
  65.     while (nop--)
  66.     {
  67.         solve();
  68.         if (nop)
  69.             cout << endl;
  70.     }
  71.     return 0;
  72. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/WMdfZw
language:
C++ (gcc 8.3)
created:
13 hours 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!