제출 #911348

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
911348		mircea_007	Wall (IOI14_wall)	C++17	100 / 100	440 ms	53420 KiB

wall

#include "wall.h"

#include <vector>
#include <algorithm>

const int MAXH = 100 * 1000;

struct Op {
  int st, dr;

  Op( int st = 0, int dr = MAXH ): st( st ), dr( dr ) {}

  int operator ()( const int &x ) const {
    if( x < st )
      return st;
    if( x > dr )
      return dr;

    return x;
  }

  Op operator + ( const Op& that ) const {
    return Op( that( st ), that( dr ) ); // SPER ca e bine (doamne ajuta)
  }
};

const int MAXK = 5e5;

struct AINT {
  Op aint[4 * MAXK];
  int aintn;

  void init( int n ) {
    aintn = 1;
    while( aintn < n )
      aintn <<= 1;

    for( int i = 2 * aintn - 1 ; i-- ; )
      aint[i] = Op( 0, MAXH );
  }

  void update( int idx, Op op ) {
    idx += aintn - 1;
    aint[idx] = op;

    while( idx ) {
      idx = (idx - 1) >> 1;

      aint[idx] = aint[idx * 2 + 1] + aint[idx * 2 + 2];
    }
  }

  Op query() { return aint[0]; } // nu e nevoie de query pe interval
} aint;

struct Event {
  Op op;
  int time;
  int idx;

  Event( int time, int idx, Op op ): time( time ), idx( idx ), op( op ) {}
};

void buildWall( int n, int k, int op[], int left[], int right[], int height[], int finalHeight[] ) {
  std::vector<Event> evt;

  for( int i = 0 ; i < k ; i++ ) {
    if( op[i] == 1 ) // adding phase
      evt.emplace_back( left[i], i, Op( height[i], MAXH ) );
    else
      evt.emplace_back( left[i], i, Op( 0, height[i] ) );

    evt.emplace_back( right[i] + 1, i, Op( 0, MAXH ) );
  }

  std::sort( evt.begin(), evt.end(), []( const Event &a, const Event &b ) -> bool {
    return a.time < b.time;
  } );

  aint.init( k );

  int last_evt = 0;
  for( int i = 0 ; i < n ; i++ ){
    while( last_evt < (int)evt.size() && evt[last_evt].time <= i ){
      aint.update( evt[last_evt].idx, evt[last_evt].op );
      last_evt++;
    }

    finalHeight[i] = aint.query()( 0 );
  }

  return;
}

컴파일 시 표준 에러 (stderr) 메시지

wall.cpp: In constructor 'Event::Event(int, int, Op)':
wall.cpp:59:7: warning: 'Event::idx' will be initialized after [-Wreorder]
   59 |   int idx;
      |       ^~~
wall.cpp:57:6: warning:   'Op Event::op' [-Wreorder]
   57 |   Op op;
      |      ^~
wall.cpp:61:3: warning:   when initialized here [-Wreorder]
   61 |   Event( int time, int idx, Op op ): time( time ), idx( idx ), op( op ) {}
      |   ^~~~~

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39