Submission #800502

#	Time	Username	Problem	Language	Result	Execution time	Memory
800502		BERNARB01	Wall (IOI14_wall)	C++17	100 / 100	856 ms	65376 KiB

wall

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

using namespace std;

#ifdef B01
#include "../deb.h"
#else
#define deb(...)
#endif

const int N = (int) 4e6 + 9;

struct node {
  int l = INT_MIN;
  int r = INT_MAX;

  void apply(int v, bool op) {
    if (op) {
      l = min(l, v);
      r = min(r, v);
    } else {
      l = max(l, v);
      r = max(r, v);
    }
  }
} tr[N];

inline void push(int x, int l, int r) {
  int y = (l + r) >> 1;
  int z = x + ((y - l + 1) << 1);
  if (tr[x].l != INT_MIN) {
    tr[x + 1].apply(tr[x].l, 0);
    tr[z].apply(tr[x].l, 0);
    tr[x].l = INT_MIN;
  }
  if (tr[x].r != INT_MAX) {
    tr[x + 1].apply(tr[x].r, 1);
    tr[z].apply(tr[x].r, 1);
    tr[x].r = INT_MAX;
  }
}

void modify(int x, int l, int r, int ll, int rr, int v, int op) {
  if (ll <= l && r <= rr) {
    tr[x].apply(v, op);
    return;
  }
  int y = (l + r) >> 1;
  int z = x + ((y - l + 1) << 1);
  push(x, l, r);
  if (ll <= y) {
    modify(x + 1, l, y, ll, rr, v, op);
  }
  if (rr > y) {
    modify(z, y + 1, r, ll, rr, v, op);
  }
}

int res[N];

inline void dfs(int x, int l, int r) {
  if (l == r) {
    res[l] = tr[x].l;
    return;
  }
  int y = (l + r) >> 1;
  int z = x + ((y - l + 1) << 1);
  push(x, l, r);
  dfs(x + 1, l, y);
  dfs(z, y + 1, r);
}

void buildWall(int n, int q, int op[], int ll[], int rr[], int h[], int finalHeight[]){
  for (int i = 0; i < n; i++) {
    modify(0, 0, n - 1, i, i, 0, 0);
    modify(0, 0, n - 1, i, i, 0, 1);
  }
  for (int i = 0; i < q; i++) {
    modify(0, 0, n - 1, ll[i], rr[i], h[i], op[i] - 1);
  }
  dfs(0, 0, n - 1);
  for (int i = 0; i < n; i++) {
    finalHeight[i] = res[i];
  }
  return;
}

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