Submission #1018813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018813		NeroZein	Wall (IOI14_wall)	C++17	100 / 100	969 ms	68164 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std; 

const int N = 2e6 + 6;

int mn[N * 2], mx[N * 2];

void build(int nd, int l, int r) {
  if (l == r) {
    return; 
  }
  mn[nd] = N; 
  mx[nd] = 0;
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  build(nd + 1, l, mid);
  build(rs, mid + 1, r); 
}

void push(int nd, int l, int r) {
  if (l == r) return;
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  for (int i : {nd + 1, rs}) {
    mx[i] = max(mx[i], mx[nd]);
    mn[i] = max(mn[i], mx[nd]);
    mx[i] = min(mx[i], mn[nd]);
    mn[i] = min(mn[i], mn[nd]); 
  }
  mn[nd] = N; mx[nd] = 0; 
}

void upd(int nd, int l, int r, int s, int e, int v, bool maximize) {
  push(nd, l, r); 
  if (l >= s && r <= e) {
    if (maximize) {
      mx[nd] = max(mx[nd], v);
      mn[nd] = max(mn[nd], v); 
    } else {
      mx[nd] = min(mx[nd], v);
      mn[nd] = min(mn[nd], v);
    }
    push(nd, l, r);
    return;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (mid >= e) {
    upd(nd + 1, l, mid, s, e, v, maximize);
  } else {
    if (mid < s) {
      upd(rs, mid + 1, r, s, e, v, maximize);       
    } else {
      upd(nd + 1, l, mid, s, e, v, maximize);
      upd(rs, mid + 1, r, s, e, v, maximize);             
    }
  }
}

int qry(int nd, int l, int r, int p) {
  push(nd, l, r); 
  if (l == r) {
    return mx[nd];
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (p <= mid) {
    return qry(nd + 1, l, mid, p);
  } else {
    return qry(rs, mid + 1, r, p); 
  }
}

void buildWall(int n, int q, int op[], int l[], int r[], int v[], int finalHeight[]) {
  build(0, 0, n - 1); 
  for (int i = 0; i < q; ++i) {
    upd(0, 0, n - 1, l[i], r[i], v[i], op[i] % 2); 
  }
  for (int i = 0; i < n; ++i) {
    finalHeight[i] = qry(0, 0, n - 1, i);
  }
  return;
}

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