Submission #692252

#	Time	Username	Problem	Language	Result	Execution time	Memory
692252		zeroesandones	Wall (IOI14_wall)	C++17	100 / 100	1064 ms	59316 KiB

wall

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

using ll = long long;
const int inf = 1e9 + 7;

struct node {
  int mn = 0, mx = inf;
};

struct SegTree {
  vector<node> tree;
  int n;

  SegTree(int N) {
    n = N;
    while(__builtin_popcountll(n) != 1) ++n;
    tree.resize(2 * n);
  }

  void prop(int v) {
    tree[2 * v].mn = min(tree[v].mx, max(tree[v * 2].mn, tree[v].mn));
    tree[2 * v].mx = max(tree[v].mn, min(tree[2 * v].mx, tree[v].mx));
    tree[2 * v + 1].mn = min(tree[v].mx, max(tree[v * 2 + 1].mn, tree[v].mn));
    tree[2 * v + 1].mx = max(tree[v].mn, min(tree[2 * v + 1].mx, tree[v].mx));
    tree[v].mn = 0;
    tree[v].mx = inf;
  }

  void update(int a, int b, int x, int y, int k, int v, int op) {
    if(a > y || b < x) return;
    if(a <= x && y <= b) {
      if(op == 1) {
        tree[k].mx = max(tree[k].mx, v);
        tree[k].mn = max(tree[k].mn, v);
      } else {
        tree[k].mx = min(tree[k].mx, v);
        tree[k].mn = min(tree[k].mn, v);
      }
      return;
    }

    prop(k);

    int d = (x + y) / 2;
    update(a, b, x, d, 2 * k, v, op);
    update(a, b, d + 1, y, 2 * k + 1, v, op);
  }

  void update(int a, int b, int v, int op) {
    update(a, b, 0, n - 1, 1, v, op);
  }

  int get(int x, int y, int k, int p) {
    if(x == y)
      return tree[k].mn;
    prop(k);

    int d = (x + y) / 2;
    if(p <= d)
      return get(x, d, 2 * k, p);
    return get(d + 1, y, 2 * k + 1, p);
  }

  int get(int p) {
    return get(0, n - 1, 1, p);
  }

  void print() {
    for(int i = 0; i < 2 * n; ++i) {
      cout << i << ' ' << tree[i].mn << ' ' << tree[i].mx << "\n";
    }
  }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
  SegTree sgt(n);

  for(int i = 0; i < k; ++i) {
    sgt.update(left[i], right[i], height[i], op[i]);
  }

  for(int i = 0; i < n; ++i) {
    finalHeight[i] = sgt.get(i);
  }
}

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