Submission #1138133

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138133		Mamedov	Wall (IOI14_wall)	C++20	0 / 100	120 ms	24648 KiB

wall

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

using namespace std;

const int MAX = (1 << 22);
int low[MAX], high[MAX];

void pushHigh(int v, int pa) {
  high[v] = min(high[v], high[pa]);
  low[v] = min(low[v], high[v]);
}

void relaxHigh(int v, int l, int r) {
  if (l != r) {
    pushHigh(v << 1, v);
    pushHigh((v << 1) | 1, v);
  }
  high[v] = MAX;
}

void pushLow(int v, int pa) {
  low[v] = max(low[v], low[pa]);
  high[v] = max(high[v], low[v]);
}

void relaxLow(int v, int l, int r) {
  if (l != r) {
    pushLow(v << 1, v);
    pushLow((v << 1) | 1, v);
  }
  low[v] = 0;
}

void relax(int v, int l, int r) {
  if (l != r) {
    if (high[v] != MAX) relaxHigh(v, l, r);
    if (low[v] != 0) relaxLow(v, l, r);
  }
}

void upd(int v, int l, int r, int ul, int ur, int h, int type) {
  if (r < ul || ur < l) return;
  relax(v, l, r);
  if (ul <= l && r <= ur) {
    (type == 1 ? (low[v] = h, high[v] = max(low[v], high[v])) : (high[v] = h, low[v] = min(low[v], high[v])));
    relax(v, l, r);
  }
  else {
    int mid = (l + r) >> 1;
    upd(v << 1, l, mid, ul, ur, h, type);
    upd((v << 1) | 1, mid + 1, r, ul, ur, h, type);
  }
}

void getAll(int v, int l, int r, int finalHeight[]) {
  if (l == r) finalHeight[l] = low[v];
  else {
    relax(v, l, r);
    int mid = (l + r) >> 1;
    getAll(v << 1, l, mid, finalHeight);
    getAll((v << 1) | 1, mid + 1, r, finalHeight);
  }
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  for (int i = 0; i < MAX; ++i) {
    high[i] = MAX;
  }
  for (int i = 0; i < k; ++i) {
    upd(1, 0, n - 1, left[i], right[i], height[i], op[i]);
  }
  getAll(1, 0, n - 1, finalHeight);
}

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