oj.uz

Submission #911348

# Submission time Handle Problem Language Result Execution time Memory
911348 2024-01-18T19:20:22 Z mircea_007 Wall (IOI14_wall) C++17
100 / 100
 440 ms 53420 KB 
#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;
}

Compilation message

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16120 KB Output is correct
2 Correct 6 ms 16476 KB Output is correct
3 Correct 5 ms 16216 KB Output is correct
4 Correct 8 ms 16604 KB Output is correct
5 Correct 8 ms 16756 KB Output is correct
6 Correct 7 ms 16476 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15964 KB Output is correct
2 Correct 174 ms 43560 KB Output is correct
3 Correct 140 ms 30396 KB Output is correct
4 Correct 342 ms 45784 KB Output is correct
5 Correct 256 ms 46776 KB Output is correct
6 Correct 232 ms 46972 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15964 KB Output is correct
2 Correct 6 ms 16476 KB Output is correct
3 Correct 5 ms 16220 KB Output is correct
4 Correct 8 ms 16476 KB Output is correct
5 Correct 8 ms 16600 KB Output is correct
6 Correct 7 ms 16476 KB Output is correct
7 Correct 4 ms 15964 KB Output is correct
8 Correct 186 ms 45108 KB Output is correct
9 Correct 133 ms 29940 KB Output is correct
10 Correct 295 ms 46408 KB Output is correct
11 Correct 258 ms 46444 KB Output is correct
12 Correct 232 ms 46688 KB Output is correct
13 Correct 5 ms 15960 KB Output is correct
14 Correct 185 ms 44328 KB Output is correct
15 Correct 25 ms 18128 KB Output is correct
16 Correct 383 ms 46952 KB Output is correct
17 Correct 256 ms 47256 KB Output is correct
18 Correct 302 ms 45240 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15964 KB Output is correct
2 Correct 6 ms 16476 KB Output is correct
3 Correct 6 ms 16472 KB Output is correct
4 Correct 9 ms 16472 KB Output is correct
5 Correct 8 ms 16792 KB Output is correct
6 Correct 8 ms 16476 KB Output is correct
7 Correct 5 ms 15960 KB Output is correct
8 Correct 178 ms 44932 KB Output is correct
9 Correct 133 ms 31372 KB Output is correct
10 Correct 297 ms 47144 KB Output is correct
11 Correct 259 ms 46272 KB Output is correct
12 Correct 241 ms 46536 KB Output is correct
13 Correct 4 ms 15964 KB Output is correct
14 Correct 217 ms 43364 KB Output is correct
15 Correct 24 ms 18200 KB Output is correct
16 Correct 363 ms 47444 KB Output is correct
17 Correct 258 ms 45244 KB Output is correct
18 Correct 262 ms 45524 KB Output is correct
19 Correct 417 ms 53416 KB Output is correct
20 Correct 391 ms 52908 KB Output is correct
21 Correct 399 ms 52904 KB Output is correct
22 Correct 398 ms 52900 KB Output is correct
23 Correct 395 ms 53252 KB Output is correct
24 Correct 383 ms 52904 KB Output is correct
25 Correct 383 ms 53420 KB Output is correct
26 Correct 397 ms 52724 KB Output is correct
27 Correct 399 ms 53416 KB Output is correct
28 Correct 418 ms 53000 KB Output is correct
29 Correct 440 ms 52656 KB Output is correct
30 Correct 392 ms 52820 KB Output is correct