제출 #1276696

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276696		turral	벽 (IOI14_wall)	C++20	100 / 100	529 ms	57936 KiB

wall

#include "wall.h"
#include <iostream>
#include <vector>

using namespace std;

const int INF = 1e18;

int log2_ceil(int n){
  return 63 - __builtin_clzll(n) + (__builtin_popcount(n) != 1);
}

inline int L(int node){
  return 2*node;
}

inline int R(int node){
  return 2*node + 1;
}

struct segment_tree {
  int numElements, N;
  vector<int> stMax, stMin;
  vector<bool> lazyAdd, lazyRemove;

  segment_tree(int _numEl) : numElements(_numEl) {
    N = (1 << log2_ceil(numElements));

    stMax.assign(2*N, -INF);
    stMin.assign(2*N, INF);

    lazyAdd.assign(2*N, false);
    lazyRemove.assign(2*N, false);

    for (int i=0; i<numElements; ++i) stMax[i+N] = stMin[i+N] = 0;
    for (int i=N-1; i>=1; --i) stMin[i] = min(stMin[L(i)], stMin[R(i)]);
    for (int i=N-1; i>=1; --i) stMax[i] = max(stMax[L(i)], stMax[R(i)]);
  }

  
  void addLazyFunc(int node, int h){
    if (stMin[node] >= h) return;

    stMin[node] = h;
    lazyAdd[node] = true;

    if (stMax[node] < h){
      stMax[node] = h;
      lazyRemove[node] = true;
    }
  }

  void removeLazyFunc(int node, int h){
    if (stMax[node] <= h) return;

    stMax[node] = h;
    lazyRemove[node] = true;

    if (stMin[node] > h){
      stMin[node] = h;
      lazyAdd[node] = true;
    }
  }

  void pushAdd(int node){
    if (node < N){
      addLazyFunc(L(node), stMin[node]);
      addLazyFunc(R(node), stMin[node]);
    }

    lazyAdd[node] = false;
  }

  void pushRemove(int node){
    if (node < N){
      removeLazyFunc(L(node), stMax[node]);
      removeLazyFunc(R(node), stMax[node]);
    }

    lazyRemove[node] = false;
  }

  void push(int node){
    if (lazyAdd[node]) pushAdd(node);
    if (lazyRemove[node]) pushRemove(node);
  }

  void remove(int node, int l, int r, int a, int b, int h){
    if (b < l || r < a) return;

    if (a <= l && r <= b){
      removeLazyFunc(node, h);
      return;
    }
    
    push(node);

    int m = (l+r)/2;
    remove(L(node), l, m, a, b, h);
    remove(R(node), m+1, r, a, b, h);

    stMin[node] = min(stMin[L(node)], stMin[R(node)]);
    stMax[node] = max(stMax[L(node)], stMax[R(node)]);
  }

  void remove(int a, int b, int h){
    remove(1, 0, N-1, a, b, h);
  }

  void add(int node, int l, int r, int a, int b, int h){
    if (b < l || r < a) return;

    if (a <= l && r <= b){
      addLazyFunc(node, h);
      return;
    }
    
    push(node);

    int m = (l+r)/2;
    add(L(node), l, m, a, b, h);
    add(R(node), m+1, r, a, b, h);

    stMin[node] = min(stMin[L(node)], stMin[R(node)]);
    stMax[node] = max(stMax[L(node)], stMax[R(node)]);
  }

  void add(int a, int b, int h){
    add(1, 0, N-1, a, b, h);
  }

  vector<int> getState(){
    vector<int> res(numElements);

    for (int i=1; i<N; ++i) push(i);
    for (int i=0; i<numElements; ++i) res[i] = stMin[i+N]; 

    return res;
  }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  segment_tree ST(n);

  for (int i=0; i<k; ++i){
    if (op[i] == 1){
      ST.add(left[i], right[i], height[i]);
    } else {
      ST.remove(left[i], right[i], height[i]);
    }
  }

  vector<int> res = ST.getState();
  for (int i=0; i<n; ++i){
    finalHeight[i] = res[i];
  } 
  return;
}

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

wall.cpp:7:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    7 | const int INF = 1e18;
      |                 ^~~~

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