oj.uz

Submission #911233

# Submission time Handle Problem Language Result Execution time Memory
911233 2024-01-18T16:34:49 Z contest_alt Wall (IOI14_wall) C++17
100 / 100
 420 ms 58488 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 5 ms 15960 KB Output is correct
2 Correct 6 ms 16476 KB Output is correct
3 Correct 6 ms 16268 KB Output is correct
4 Correct 8 ms 16476 KB Output is correct
5 Correct 7 ms 16476 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 15960 KB Output is correct
2 Correct 177 ms 46540 KB Output is correct
3 Correct 135 ms 32192 KB Output is correct
4 Correct 342 ms 51492 KB Output is correct
5 Correct 259 ms 51852 KB Output is correct
6 Correct 259 ms 49360 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 16472 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 16476 KB Output is correct
6 Correct 8 ms 16476 KB Output is correct
7 Correct 5 ms 15960 KB Output is correct
8 Correct 174 ms 46320 KB Output is correct
9 Correct 137 ms 32700 KB Output is correct
10 Correct 306 ms 50104 KB Output is correct
11 Correct 266 ms 50616 KB Output is correct
12 Correct 231 ms 49040 KB Output is correct
13 Correct 5 ms 15960 KB Output is correct
14 Correct 181 ms 48092 KB Output is correct
15 Correct 24 ms 18132 KB Output is correct
16 Correct 358 ms 51896 KB Output is correct
17 Correct 258 ms 50636 KB Output is correct
18 Correct 285 ms 50908 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 5 ms 16220 KB Output is correct
4 Correct 8 ms 16472 KB Output is correct
5 Correct 9 ms 16476 KB Output is correct
6 Correct 8 ms 16476 KB Output is correct
7 Correct 5 ms 15964 KB Output is correct
8 Correct 178 ms 46108 KB Output is correct
9 Correct 135 ms 32468 KB Output is correct
10 Correct 301 ms 50872 KB Output is correct
11 Correct 253 ms 51560 KB Output is correct
12 Correct 237 ms 49592 KB Output is correct
13 Correct 4 ms 15964 KB Output is correct
14 Correct 182 ms 46908 KB Output is correct
15 Correct 26 ms 18128 KB Output is correct
16 Correct 349 ms 51132 KB Output is correct
17 Correct 257 ms 50232 KB Output is correct
18 Correct 275 ms 51096 KB Output is correct
19 Correct 408 ms 57916 KB Output is correct
20 Correct 398 ms 57836 KB Output is correct
21 Correct 406 ms 58024 KB Output is correct
22 Correct 390 ms 58272 KB Output is correct
23 Correct 414 ms 57748 KB Output is correct
24 Correct 407 ms 57804 KB Output is correct
25 Correct 386 ms 57988 KB Output is correct
26 Correct 418 ms 58284 KB Output is correct
27 Correct 420 ms 57980 KB Output is correct
28 Correct 400 ms 57768 KB Output is correct
29 Correct 391 ms 57820 KB Output is correct
30 Correct 396 ms 58488 KB Output is correct