Submission #991962

#	Time	Username	Problem	Language	Result	Execution time	Memory
991962		phoenix	Wall (IOI14_wall)	C++17	100 / 100	594 ms	77868 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

const int N = (1 << 21);
const int INF = 1e9;

int tr_min[2 * N];
int tr_max[2 * N];

void setpush(int v, int l, int r) {
  tr_min[v] = max(tr_min[v], l);
  tr_min[v] = min(tr_min[v], r);
  tr_max[v] = max(tr_max[v], l);
  tr_max[v] = min(tr_max[v], r);
}

void push(int v) {
  if (v >= N) return;
  setpush(2 * v, tr_min[v], tr_max[v]);
  setpush(2 * v + 1, tr_min[v], tr_max[v]);
}

void update(int ql, int qr, int lb, int rb, int l = 0, int r = N - 1, int v = 1) {
  if (r < ql || l > qr)
    return;
  if (ql <= l && r <= qr) {
    setpush(v, lb, rb);
    return;
  }
  push(v);
  int mid = (l + r) / 2;
  update(ql, qr, lb, rb, l, mid, 2 * v);
  update(ql, qr, lb, rb, mid + 1, r, 2 * v + 1);
  tr_min[v] = min(tr_min[2 * v], tr_min[2 * v + 1]);
  tr_max[v] = max(tr_max[2 * v], tr_max[2 * v + 1]);
}

int arr[N];
void construct(int l = 0, int r = N - 1, int v = 1) {
  if (l == r) {
    arr[l] = tr_min[v];
    return;
  }
  push(v);
  int mid = (l + r) / 2;
  construct(l, mid, 2 * v);
  construct(mid + 1, r, 2 * v + 1);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  for (int i = 0; i < k; i++) {
    if (op[i] == 1) {
      update(left[i], right[i], height[i], INF);
    } else {
      update(left[i], right[i], 0, height[i]);
    }
  }
  construct();
  for (int i = 0; i < n; i++)
    finalHeight[i] = arr[i];
  return;
}

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