Submission #1319235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319235		tsetsenbileg	Wall (IOI14_wall)	C++20	0 / 100	97 ms	8044 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using pr = pair<int, int>;
const int INF = 1e9+7, MOD = 1e9+7;
vector<int> a;

struct segtree{
  vector<int> st, up, down;
  int n;
  void init(int N) {
    n = N;
    st.assign(4*n, 0);
    down.assign(4*n, -1);
    up.assign(4*n, -1);
  }
  int L(int i) {return i << 1;}
  int R(int i) {return i << 1 | 1;}
  void push(int i, int l, int r) {
    if (up[i] == -1 && down[i] == -1) return;
    if (up[i] != -1) {
      if (l == r) {
        st[i] = max(up[i], st[i]);
      }
      else {
        up[L(i)] = up[i];
        up[R(i)] = up[i];
      }
    }
    if (down[i] != -1) {
      if (l == r) {
        st[i] = min(st[i], down[i]);
      }
      else {
        down[L(i)] = down[i];
        down[R(i)] = down[i];
      }
    }
    down[i] = -1;
    up[i] = -1;
  }
  void update(int i, int l, int r, int ll, int rr, int op, int h) {
    push(i, l, r);
    if (r < ll || l > rr) return;
    if (ll <= l && r <= rr) {
      if (op == 1) up[i] = h;
      else down[i] = h;
      return;
    }
    int m = (l + r) >> 1;
    update(L(i), l, m, ll, rr, op, h);
    update(R(i), m+1, r, ll, rr, op, h);
  }
  void query(int i, int l, int r) {
    push(i, l, r);
    if (l == r) {
      a[l] = st[i];
      return;
    }
    int m = (l + r) >> 1;
    query(L(i), l, m);
    query(R(i), m + 1, r);
  }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  segtree seg;
  a.resize(n+1);
  seg.init(n);
  for (int i = 0; i < k; i++) {
    seg.update(1, 1, n, left[i]+1, right[i]+1, op[i], height[i]);
    // seg.query(1, 1, n);
  // for (int j = 0; j < n; j++) {
  //   finalHeight[j] = a[j+1];
  // }
  // for (int j = 1; j <= n; j++)
  //   cout << j << ' ' << a[j] << '\n';
  }
  seg.query(1, 1, n);
  for (int i = 0; i < n; i++) {
    finalHeight[i] = a[i+1];
  }
  return;
}

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