fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using  namespace std ;
  3. int  n , a , m ;
  4. set < int > inuse ;
  5. vector < int > adj [111111] ;
  6. int order [111111] ;
  7. typedef pair < int , int > ii ;
  8. #define P first
  9. #define Q second
  10. int main(){
  11.     int  i , j, k, l , ans ;
  12.     ans= 0 ; 
  13.    while (  scanf("%d %d %d", &n , &a , &m) != EOF ) { ;
  14.     ans = 0 ; inuse.clear() ;
  15.     for ( i = 0 ; i < m ; i++)
  16.     {
  17.          scanf("%d",&order[i]);
  18.          adj[ order[i] ].push_back(i) ;
  19.     }
  20. int cap = 0 ;
  21. priority_queue < ii , vector  < ii > , less <ii> > pq ;
  22.     for ( i = 0 ; i < m ; i++){
  23.  
  24.         int x = order[i] ;
  25.         set < int > :: iterator fit ;
  26.         fit = lower_bound ( inuse.begin() , inuse.end() , x) ;
  27.         if( fit !=  inuse.end())  
  28.         if( *fit == x )
  29.         {
  30.             vector < int > :: iterator it ;
  31.             it = lower_bound( adj[x].begin() , adj[x].end() , i+1) ;
  32.             if( it != adj[x].end())
  33.             pq.push(ii(*it,x));
  34.             else
  35.             pq.push(ii(1e9,x)) ;
  36.            // cout << i <<" found  "<<x << endl ;
  37.             continue ;
  38.         }
  39.  
  40.         if ( cap < n ){
  41.             inuse.insert(x);
  42.             ans++ ; cap++ ; 
  43.             vector < int > :: iterator it ;
  44.             it = lower_bound( adj[x].begin() , adj[x].end() , i+1) ;
  45.             if( it != adj[x].end())
  46.             pq.push(ii(*it,x)) ;
  47.             else
  48.             pq.push(ii(1e9,x)) ;
  49.            // cout << i << " insert " << x << endl;
  50.             continue ;
  51.         }
  52.        ans++ ;
  53.  
  54.        ii y = pq.top() ; pq.pop() ;
  55.        //cout <<x <<" "<< y.P <<" romve->"<<y.Q << endl;
  56.        fit = lower_bound( inuse.begin() , inuse.end() , y.Q);
  57.        inuse.erase(fit) ;
  58.        inuse.insert(x) ;
  59.        vector<int> :: iterator it ;
  60.        it = lower_bound( adj[x].begin() , adj[x].end() , i+1);
  61.        if( it != adj[x].end())
  62.        pq.push(ii(*it,x)) ;
  63.        else
  64.        pq.push(ii(1e9,x)) ;
  65.       // cout << i <<" "<< ans << endl ; 
  66.     }
  67.   printf("%d\n",ans) ;
  68. }
  69.   return 0 ;
  70. }
Success #stdin #stdout 0s 5172KB
comments (?)
stdin
copy 
1 2 3
0
0
1
3 4 8
0
1
2
3
3
2
1
0
stdout
copy 
2
5
https://ideone.com/UThJix
language:
C++14 (gcc 8.3)
created:
9 years 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!