Advertisement
kadeyrov

Untitled

Dec 3rd, 2020
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.88 KB | None | 0 0
  1. #include <vector>
  2. #include <iostream>
  3. #include <limits>
  4. using namespace std;
  5.  
  6. vector<int> minSuf(vector<int> a) {
  7.    
  8.     vector<int> ans;
  9.     reverse(a.begin(), a.end());
  10.    
  11.     for (int i = 0; i < a.size(); i++) {
  12.         if (!i) {
  13.             ans.push_back(a[i]);
  14.         } else {
  15.             ans.push_back(min(a[i], ans[i - 1]));
  16.         }
  17.     }
  18.    
  19.     reverse(ans.begin(), ans.end());
  20.    
  21.     return ans;
  22. }
  23.  
  24. // 1 2 0 3 4
  25. // 1 1
  26.  
  27. int main() {
  28.     int t;
  29.     cin >> t;
  30.    
  31.     while(t--) {
  32.         int n;
  33.         cin >> n;
  34.         vector<int> a(n);
  35.         for (int i = 0; i < n; i++)
  36.             cin >> a[i];
  37.        
  38.         vector<int> suf = minSuf(a);
  39.        
  40.         int ans = 0;
  41.         for (int i = 0; i < n - 1; i++) {
  42.             if (a[i] > suf[i + 1])
  43.                 ans++;
  44.         }
  45.        
  46.         cout << ans << endl;
  47.     }
  48. }
  49.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement