Submission #1302946

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302946		vincentbucourt1	Wall (IOI14_wall)	C++20	100 / 100	743 ms	48880 KiB

wall

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

const int OO = (int)1e18;

struct SegMonoid {
  int lo = 0, hi = 0;
  SegMonoid (int initLo, int initHi) {
    lo = initLo, hi = initHi;
  }
  void combineNew (SegMonoid other) {
    if (hi < other.lo) {
      lo = other.lo, hi = other.lo;
    }
    else if (other.hi < lo) {
      lo = other.hi, hi = other.hi;
    }
    else {
      lo = max(lo, other.lo), hi = min(hi, other.hi);
    }
  }
  void print () {
    cerr << "[" << lo << ", " << hi << "]";
  }
};
SegMonoid combineSegMonoid (SegMonoid a, SegMonoid b) {
  return SegMonoid(min(a.lo, b.lo), max(a.hi, b.hi));
}
struct Segtree {
  int numleaves;
  vector<SegMonoid> tree;
  Segtree (int n) {
    numleaves = 1;
    while (numleaves < n) numleaves *= 2;
    tree.assign(2*numleaves, SegMonoid(0, 0));
  }
  void pushdown (int node) {
    if (node < numleaves) {
      tree[2*node].combineNew(tree[node]);
      tree[2*node+1].combineNew(tree[node]);
    }
  }
  void update (int node, int nL, int nR, int qL, int qR, SegMonoid newInter) {
    pushdown(node);
    if (qL <= nL && nR <= qR) {
      tree[node].combineNew(newInter);
      pushdown(node);
    }
    else if (nR < qL || qR < nL) {
      return;
    }
    else {
      int nMid = nL + (nR - nL) / 2;
      update(2*node, nL, nMid, qL, qR, newInter);
      update(2*node+1, nMid+1, nR, qL, qR, newInter);
      tree[node] = combineSegMonoid(tree[2*node], tree[2*node+1]);
    }
  }
  void update (int qL, int qR, SegMonoid newInter) {
    update(1, 0, numleaves-1, qL, qR, newInter);
  }
  int get (int idx) {
    int node = 1, nL = 0, nR = numleaves-1;
    while (node < numleaves) {
      pushdown(node);
      int nMid = nL + (nR - nL) / 2;
      if (nL <= idx && idx <= nMid) {
        nR = nMid;
        node = 2*node;
      }
      else {
        nL = nMid+1;
        node = 2*node+1;
      }
    }
    return tree[node].lo;
  }
  void dbg () {
    cerr << "Tree:\n";
    for (int h = 0; h <= log2(numleaves); h++) {
      for (int i = (1 << h); i < (1 << (h+1)); i++) {
        tree[i].print();cerr << " ";
      }
      cerr << "\n";
    }
    cerr << "Wall:\n";
    for (int i = 0; i < numleaves; i++) cerr << get(i) << " ";
    cerr << "\n";
  }
};

void buildWall(int N, int Q, int typeQ[], int leftQ[], int rightQ[], int heightQ[], int finalHeight[]){
  Segtree wall(N);
  for (int q = 0; q < Q; q++) {
    if (typeQ[q] == 1) { // add
      wall.update(leftQ[q], rightQ[q], SegMonoid(heightQ[q], OO));
    }
    else { // rem
      wall.update(leftQ[q], rightQ[q], SegMonoid(0, heightQ[q]));
    }
  }
  for (int i = 0; i < N; i++) {
    finalHeight[i] = wall.get(i);
  }
}

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