Submission #1276691

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276691		turral	Wall (IOI14_wall)	C++20	Compilation error	0 ms	0 KiB

wall

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

using namespace std;

#define int long long

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;
}

/*
signed main(){
  int N, K; cin >> N >> K;

  int op[K], l[K], r[K], h[K], nh[N];
  for (int i=0; i<K; ++i){
    cin >> op[i] >> l[i] >> r[i] >> h[i];
  }

  buildWall(N, K, op, l, r, h, nh);
}
*/

Compilation message (stderr)

/usr/bin/ld: /tmp/ccdDDdhD.o: in function `main':
grader.cpp:(.text.startup+0x123): undefined reference to `buildWall(int, int, int*, int*, int*, int*, int*)'
collect2: error: ld returned 1 exit status