Submission #51767

#	Time	Username	Problem	Language	Result	Execution time	Memory
51767		model_code	Employment (JOI16_employment)	C++17	100 / 100	426 ms	9248 KiB

employment

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

class BIT{
private:
  vector<int> dat;
  int size;
public:
  void init( int n ){
    size = 1;
    while( size < n ) size *= 2;
    dat = vector<int>( size , 0 );
  }
  void add( int k , int v ){
    for( int i = k+1; i <= size; i += i & -i ) dat[i-1] += v;
  }
  int sum( int k ){ // [ 0 , k ]
    int res = 0;
    for( int i = k+1; i > 0; i -= i & -i ) res += dat[i-1];
    return res;
  }
};

vector<int> compress( vector<int> compress_array ){
  vector<int> ord = compress_array, res(0);
  sort( ord.begin() , ord.end() );
  ord.erase( unique( ord.begin() , ord.end() ) , ord.end() );
  for( int i = 0; i < compress_array.size(); i++ ) res.push_back( lower_bound( ord.begin() , ord.end() , compress_array[i] ) - ord.begin() );
  return res;
}

const int OUTPUT_QUERY = 1;
const int UPDATE_QUERY = 2;
const int MAX_N = 200000;
const int MAX_M = 200000;

int n, m;
BIT bit;
vector<int> vals, compressed;
int val[MAX_N+2], type[MAX_M], pos[MAX_M];

void add( int l , int r , int v ){ // [ l , r )
  bit.add( l , v );
  bit.add( r , -v );
}

int get( int k ){
  return bit.sum( k );
}

void update( int pos , int new_val ){
  int neighbor_min = min( val[pos-1] , val[pos+1] );
  int neighbor_max = max( val[pos-1] , val[pos+1] );
  
  if( val[pos] < new_val ){ // up
    if( val[pos] < neighbor_min ) add( val[pos] + 1 , min( neighbor_min , new_val ) + 1 , -1 );
    if( new_val  > neighbor_max ) add( max( val[pos] , neighbor_max ) + 1 , new_val + 1 , 1  );
  } else if( val[pos] > new_val ){ // down
    if( val[pos] > neighbor_max ) add( max( neighbor_max , new_val ) + 1 , val[pos] + 1 , -1 );
    if( new_val  < neighbor_min ) add( new_val + 1 , min( val[pos] , neighbor_min ) + 1 , 1  );
  }
  
  val[pos] = new_val;
}

void output( int threshold ){
  printf( "%d\n" , get( threshold ) );
}

int main(){

  scanf( "%d %d" , &n , &m );

  vals = vector<int>( n+m+1 , 0 );
  for( int i = 0; i < n; i++ ) scanf( "%d" , &vals[i] );
  for( int i = 0; i < m; i++ ){
    scanf( "%d" , &type[i] );
    if( type[i] == OUTPUT_QUERY ){
      scanf( "%d" , &vals[n+i] );
    } else if( type[i] == UPDATE_QUERY ){
      scanf( "%d %d" , &pos[i] , &vals[n+i] );
    }
  }

  compressed = compress( vals );

  bit.init( n+m+1 );
  for( int i = 0; i < n; i++ ) update( i+1 , compressed[i] );

  for( int i = 0; i < m; i++ ){
    if( type[i] == OUTPUT_QUERY ) output( compressed[n+i] );    
    else if( type[i] == UPDATE_QUERY ) update( pos[i] , compressed[n+i] );
  }
  
  return 0;
}

Compilation message (stderr)

employment.cpp: In function 'std::vector<int> compress(std::vector<int>)':
employment.cpp:31:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for( int i = 0; i < compress_array.size(); i++ ) res.push_back( lower_bound( ord.begin() , ord.end() , compress_array[i] ) - ord.begin() );
                   ~~^~~~~~~~~~~~~~~~~~~~~~~
employment.cpp: In function 'int main()':
employment.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf( "%d %d" , &n , &m );
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
employment.cpp:78:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for( int i = 0; i < n; i++ ) scanf( "%d" , &vals[i] );
                                ~~~~~^~~~~~~~~~~~~~~~~~~
employment.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf( "%d" , &type[i] );
     ~~~~~^~~~~~~~~~~~~~~~~~~
employment.cpp:82:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf( "%d" , &vals[n+i] );
       ~~~~~^~~~~~~~~~~~~~~~~~~~~
employment.cpp:84:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf( "%d %d" , &pos[i] , &vals[n+i] );
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60