/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 1ms 532.0 KiB
#3 Accepted 1ms 532.0 KiB
#4 Accepted 1ms 532.0 KiB
#5 Accepted 1ms 532.0 KiB
#6 Accepted 1ms 532.0 KiB
#7 Accepted 1ms 524.0 KiB
#8 Accepted 1ms 532.0 KiB
#9 Accepted 1ms 324.0 KiB
#10 Accepted 1ms 344.0 KiB
#11 Accepted 1ms 532.0 KiB
#12 Accepted 1ms 320.0 KiB
#13 Accepted 1ms 532.0 KiB
#14 Accepted 1ms 480.0 KiB
#15 Accepted 1ms 496.0 KiB
#16 Accepted 1ms 340.0 KiB
#17 Accepted 1ms 532.0 KiB
#18 Accepted 1ms 484.0 KiB
#19 Accepted 1ms 532.0 KiB
#20 Accepted 1ms 532.0 KiB
#21 Accepted 1ms 348.0 KiB
#22 Accepted 1ms 480.0 KiB
#23 Accepted 1ms 532.0 KiB
#24 Accepted 1ms 544.0 KiB
#25 Accepted 1ms 532.0 KiB
#26 Accepted 1ms 532.0 KiB
#27 Accepted 2ms 324.0 KiB
#28 Accepted 2ms 532.0 KiB
#29 Accepted 3ms 532.0 KiB
#30 Accepted 4ms 532.0 KiB
#31 Accepted 4ms 536.0 KiB
#32 Accepted 4ms 532.0 KiB
#33 Accepted 4ms 532.0 KiB
#34 Accepted 4ms 532.0 KiB
#35 Accepted 4ms 532.0 KiB
#36 Accepted 4ms 532.0 KiB
#37 Accepted 5ms 348.0 KiB
#38 Accepted 4ms 536.0 KiB
#39 Accepted 4ms 532.0 KiB
#40 Accepted 4ms 532.0 KiB
#41 Accepted 6ms 532.0 KiB
#42 Accepted 6ms 608.0 KiB
#43 Accepted 6ms 628.0 KiB
#44 Accepted 6ms 532.0 KiB
#45 Accepted 6ms 532.0 KiB
#46 Accepted 6ms 532.0 KiB
#47 Accepted 5ms 532.0 KiB
#48 Accepted 6ms 532.0 KiB
#49 Accepted 6ms 616.0 KiB
#50 Accepted 5ms 532.0 KiB
#51 Accepted 6ms 532.0 KiB
#52 Accepted 5ms 580.0 KiB
#53 Accepted 6ms 532.0 KiB
#54 Accepted 6ms 576.0 KiB
#55 Accepted 6ms 768.0 KiB
#56 Accepted 6ms 532.0 KiB
#57 Accepted 5ms 532.0 KiB
#58 Accepted 6ms 532.0 KiB
#59 Accepted 6ms 532.0 KiB
#60 Accepted 5ms 536.0 KiB
#61 Accepted 17ms 788.0 KiB
#62 Accepted 12ms 788.0 KiB
#63 Accepted 12ms 788.0 KiB
#64 Accepted 13ms 788.0 KiB
#65 Accepted 13ms 788.0 KiB
#66 Accepted 13ms 788.0 KiB
#67 Accepted 12ms 740.0 KiB
#68 Accepted 13ms 788.0 KiB
#69 Accepted 12ms 916.0 KiB
#70 Accepted 12ms 788.0 KiB
#71 Accepted 27ms 1020.0 KiB
#72 Accepted 8ms 1.02 MiB
#73 Accepted 9ms 1.02 MiB
#74 Accepted 12ms 1.098 MiB
#75 Accepted 13ms 1.02 MiB
#76 Accepted 13ms 1.164 MiB
#77 Accepted 11ms 1.02 MiB
#78 Accepted 14ms 1.02 MiB
#79 Accepted 15ms 1.02 MiB
#80 Accepted 14ms 1.02 MiB
#81 Accepted 27ms 1.094 MiB
#82 Accepted 13ms 1.066 MiB
#83 Accepted 11ms 1.227 MiB
#84 Accepted 11ms 1.27 MiB
#85 Accepted 22ms 1.145 MiB
#86 Accepted 9ms 1.27 MiB
#87 Accepted 8ms 1.062 MiB
#88 Accepted 9ms 1.254 MiB
#89 Accepted 11ms 1.09 MiB
#90 Accepted 11ms 1.27 MiB
#91 Accepted 124ms 6.52 MiB
#92 Accepted 82ms 6.57 MiB
#93 Accepted 77ms 6.52 MiB
#94 Accepted 88ms 6.52 MiB
#95 Accepted 90ms 6.504 MiB
#96 Accepted 95ms 6.637 MiB
#97 Accepted 63ms 6.484 MiB
#98 Accepted 79ms 6.566 MiB
#99 Accepted 78ms 6.57 MiB
#100 Accepted 76ms 6.52 MiB

Code

#include <bits/stdc++.h>
#define ll long long int
#define N "\n"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> 
//erase not possible when we are using [less equal]  instead of [less]

//order_of_key (k) : Number of items strictly smaller than k .
//find_by_order(k) : K-th element in a set (counting from zero).
  
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin>>n;
    vector<ll>a(n);
    for(ll i=0;i<n;i++){
        cin>>a[i];
    }
    ordered_set s;
    vector<ll>vis(n,0);
    ll ans=0;

    for(ll i=n-1;i>=0;i--){
      ll items=(n-i)-s.order_of_key(a[i])-1;
      if(items>=a[i]){
            ans++;
            vis[i]=1;
      }
      s.insert(a[i]);
    }
    s.clear();
    for(ll i=0;i<n;i++){
      if(vis[i]==0){
            ll items=s.order_of_key(a[i]+1);
            if(items>=a[i]){
                  ans++;
            }
      }
      s.insert(a[i]);
    }
    cout<<ans<<N;
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1184 The Curious Kid and the Number Game
Contest
Brain Booster #9
Language
C++17 (G++ 13.2.0)
Submit At
2025-04-06 16:46:55
Judged At
2025-04-06 16:46:55
Judged By
Score
100
Total Time
124ms
Peak Memory
6.637 MiB