fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long int;
  4. #define inf 1000000000000000LL
  5. #define mod 1000000007LL
  6. #define FOR(i,a,b) for(int i = a; i < b; i++)
  7.  
  8. void solve() {
  9.     ll n;
  10.     cin >> n;
  11.     vector <ll> l1(n);
  12.     vector <vector <ll>>adj(n+1);
  13.     vector <ll> cnt(n+1,0); ll mex = 0;
  14.     for (int i = 0; i < n; i++){
  15.         cin >> l1[i];
  16.         if (l1[i] <= n)
  17.             adj[l1[i]].push_back(i);
  18.     }
  19.     ll v =0; 
  20.     for (int i = 0; i < n; i++){
  21.         v += (l1[i] > 0);
  22.     }
  23.     if (adj[0].size() ==0){
  24.         cout << v << "\n"; return;
  25.     }
  26.     auto update_mex = [&](){
  27.         while (cnt[mex] >= 1){
  28.             mex++;
  29.         }
  30.     };
  31.     for (int i = n-1; i >= 0; i--){
  32.         update_mex();
  33.         if (i < adj[0][0]){
  34.             if (l1[i] < mex){
  35.                 cout << v << "\n";
  36.                 return;
  37.             }
  38.         }
  39.         if (l1[i] != 0 && l1[i] <= n){
  40.             cnt[l1[i]]++;
  41.         }
  42.         if (i == adj[0][0]){
  43.             cnt[0]++;
  44.             continue;
  45.         }
  46.     }
  47.     cout << v + 1 << "\n";
  48. }
  49.  
  50. int main() {
  51.     ios::sync_with_stdio(false);
  52.     cin.tie(nullptr);
  53.  
  54.     ll t = 1;
  55.     cin >> t;
  56.     while (t--) {
  57.         solve();
  58.     }
  59.  
  60.     return 0;
  61. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/wQllGy
language:
C++14 (clang 8.0)
created:
1 hour ago
visibility:
secret

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!