fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  3. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  4. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  5. #define ll long long
  6. #define el "\n"
  7. #define fi first
  8. #define se second
  9. #define M 1000000007
  10. #define MAXN 1000001
  11. #define NAME "dizalo"
  12. using namespace std;
  13.  
  14. ll n, m, q ;
  15. ll a[MAXN] ;
  16. ll anhxa[MAXN ] ; // vị trí mong muốn
  17. bool del[MAXN ] ;
  18.  
  19. ll calc() {
  20.     vector<ll > arr ;  
  21.     arr.push_back(0) ;
  22.     FOR(i, 1, n ) if(del[i] == false ) arr.push_back(a[i] ) ;
  23.     ll sz = arr.size() - 1 ;
  24.  
  25.     FOR(i , 1 , sz ) anhxa[arr[i]] = i ;
  26.  
  27.     set<ll> alive ;
  28.     ll ans = 0 ;
  29.     FOR(cur, 1, n  ) {
  30.         ll p = anhxa[cur ] ;
  31.         if(p == - 1 ) continue ;
  32.         auto it = alive.lower_bound(p ) ;
  33.         if(it != alive.end() ) ans ++ ;
  34.         else {
  35.             ans += p - alive.size() ;
  36.         }
  37.         alive.insert(p) ;
  38.     }
  39.  
  40.     FOR(i , 1 , sz ) anhxa[arr[i]] = - 1 ;
  41.  
  42.     return ans ;
  43. }
  44.  
  45. void init() {
  46.     cin >> n >> q ;
  47.     FOR(i, 1, n ) cin >> a[i]  ;
  48. }
  49.  
  50. void solve() {
  51.     memset(anhxa , -1 , sizeof anhxa ) ;
  52.     cout << calc( ) << " " ;
  53.     FOR(i, 1, q ) {
  54.         ll x ;
  55.         cin >> x ;
  56.         del[x] = true ;
  57.         cout << calc() << " " ;
  58.     }
  59.     cout << el ;
  60. }
  61.  
  62. int main() {
  63.     freopen(NAME".inp" , "r" , stdin);
  64.     freopen(NAME".out" , "w", stdout) ;
  65.     ios_base::sync_with_stdio(0);
  66.     cin.tie(0);
  67.     cout.tie(0);
  68.     int t = 1; // cin >> t ;
  69.     while(t--) {
  70.         init();
  71.         solve();
  72.     }
  73.     return (0&0);
  74. }
Success #stdin #stdout 0.01s 12164KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zg3aLs
language:
C++14 (gcc 8.3)
created:
7 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!