Submission #647634

#	Time	Username	Problem	Language	Result	Execution time	Memory
647634		alvinpiter	Wall (IOI14_wall)	C++17	100 / 100	896 ms	89132 KiB

wall

/*
Segment tree with lazy propagation.

At each node, maintain the following information:
mini -> Largest "at least val" operation.
maxi -> Smallest "at most val" operation.

When pushing down the value down the tree, update with the following formula:
miniChild = min(maxiParent, max(miniChild, miniParent));
maxiChild = max(miniParent, min(maxiChild, maxiParent));
*/

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define INF 1000000000
#define MAXN 2000000

struct Node {
  int mini, maxi;
  Node(int mini_ = 0, int maxi_ = INF): mini(mini_), maxi(maxi_) {}
};

int N;
Node lazy[4 * MAXN + 3];

void pushDown(int nodeNum) {
  lazy[2 * nodeNum] = Node(
    min(lazy[nodeNum].maxi, max(lazy[2 * nodeNum].mini, lazy[nodeNum].mini)),
    max(lazy[nodeNum].mini, min(lazy[2 * nodeNum].maxi, lazy[nodeNum].maxi))
  );

  lazy[2 * nodeNum + 1] = Node(
    min(lazy[nodeNum].maxi, max(lazy[2 * nodeNum + 1].mini, lazy[nodeNum].mini)),
    max(lazy[nodeNum].mini, min(lazy[2 * nodeNum + 1].maxi, lazy[nodeNum].maxi))
  );

  lazy[nodeNum] = Node(0, INF);
}

void doUpdate(int nodeNum, int l, int r, int type, int ql, int qr, int val) {
  if (qr < l || ql > r) {
    return;
  }

  if (l >= ql && r <= qr) {
    if (type == 1) {
      // "at least val"
      lazy[nodeNum].mini = max(lazy[nodeNum].mini, val);
      lazy[nodeNum].maxi = max(lazy[nodeNum].maxi, val);
    } else if (type == 2) {
      // "at most val"
      lazy[nodeNum].mini = min(lazy[nodeNum].mini, val);
      lazy[nodeNum].maxi = min(lazy[nodeNum].maxi, val);
    }

    return;
  }

  pushDown(nodeNum);

  int m = (l + r)/2;
  doUpdate(2 * nodeNum, l, m, type, ql, qr, val);
  doUpdate(2 * nodeNum + 1, m + 1, r, type, ql, qr, val);
}

void update(int type, int ql, int qr, int val) {
  doUpdate(1, 1, N, type, ql, qr, val);
}

int doQuery(int nodeNum, int l, int r, int idx) {
  if (l == r) {
    return lazy[nodeNum].mini;
  }

  pushDown(nodeNum);

  int m = (l + r)/2;
  if (idx <= m) {
    return doQuery(2 * nodeNum, l, m, idx);
  } else {
    return doQuery(2 * nodeNum + 1, m + 1, r, idx);
  }
}

int query(int idx) {
  return doQuery(1, 1, N, idx);
}

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

  // Initialize tree
  for (int i = 1; i <= 4 * N; i++) {
    lazy[i] = Node(0, INF);
  }

  for (int i = 0; i < k; i++) {
    update(op[i], left[i] + 1, right[i] + 1, height[i]);
  }

  for (int i = 0; i < n; i++) {
    finalHeight[i] = query(i + 1);
  }

  return;
}

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