Submission #1187604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187604		kunzaZa183	Wall (IOI14_wall)	C++20	100 / 100	530 ms	96848 KiB

wall

#include "wall.h"

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

int n;
vector<pair<int, int>> lazy;
vector<int> last;

void lz(int curin, int curl, int curr) {
  if (curl == curr) {
    if (last[curl] < lazy[curin].first) {
      last[curl] = lazy[curin].first;
    } else if (last[curl] > lazy[curin].second) {
      last[curl] = lazy[curin].second;
    }
    lazy[curin] = {0, INT_MAX};
    return;
  }

  if (lazy[curin * 2 + 1].second < lazy[curin].first) {
    lazy[curin * 2 + 1] = {lazy[curin].first, lazy[curin].first};
  } else if (lazy[curin].second < lazy[curin * 2 + 1].first) {
    lazy[curin * 2 + 1] = {lazy[curin].second, lazy[curin].second};
  } else {
    lazy[curin * 2 + 1] = {max(lazy[curin].first, lazy[curin * 2 + 1].first),
                           min(lazy[curin].second, lazy[curin * 2 + 1].second)};
  }

  if (lazy[curin * 2 + 2].second < lazy[curin].first) {
    lazy[curin * 2 + 2] = {lazy[curin].first, lazy[curin].first};
  } else if (lazy[curin].second < lazy[curin * 2 + 2].first) {
    lazy[curin * 2 + 2] = {lazy[curin].second, lazy[curin].second};
  } else {
    lazy[curin * 2 + 2] = {max(lazy[curin].first, lazy[curin * 2 + 2].first),
                           min(lazy[curin].second, lazy[curin * 2 + 2].second)};
  }

  lazy[curin] = {0, INT_MAX};
}

int ql, qr;
pair<int, int> qry;
void update(int curin = 0, int curl = 0, int curr = n - 1) {
  lz(curin, curl, curr);

  if (qr < curl || ql > curr) return;

  if (ql <= curl && curr <= qr) {
    lazy[curin] = qry;
    lz(curin, curl, curr);
    return;
  }

  update(curin * 2 + 1, curl, (curl + curr) / 2),
      update(curin * 2 + 2, (curl + curr) / 2 + 1, curr);
}

void ans(int curin = 0, int curl = 0, int curr = n - 1) {
  lz(curin, curl, curr);

  if (curl == curr) {
    return;
  }

  ans(curin * 2 + 1, curl, (curl + curr) / 2),
      ans(curin * 2 + 2, (curl + curr) / 2 + 1, curr);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[],
               int finalHeight[]) {
  lazy = vector<pair<int, int>>(4 * n, {0, INT_MAX});
  ::n = n;
  last = vector<int>(n, 0);

  for (int i = 0; i < k; i++) {
    ql = left[i], qr = right[i];
    if (op[i] == 1) {
      qry = {height[i], INT_MAX};
    } else {
      qry = {0, height[i]};
    }
    update();
  }

  ans();

  for (int i = 0; i < n; i++) finalHeight[i] = last[i];
}

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