Submission #1256177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256177		attky	벽 (IOI14_wall)	C++20	100 / 100	428 ms	56720 KiB

wall

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

using namespace std;

struct inter {
  int deb, fin;

  int mid() {
    return (deb+fin)/2;
  }

  inter left() {
    return {deb, mid()};
  }

  inter right() {
    return {mid()+1, fin};
  }

  bool contain(inter other) {
    return (deb <= other.deb && other.fin <= fin);
  }

  bool intersect(inter other) {
    return !(other.fin < deb || other.deb > fin);
  }

  inter intersection(inter other) {
    if(intersect(other)) {
      return {max(deb, other.deb), min(fin, other.fin)};
    }
    if(other.fin < deb) {
      return {other.fin, other.fin};
    }
    return {other.deb, other.deb};
  }
};

struct SegTree {
  int n = 1;
  inter zero = {0, int(1e9)};
  vector<inter> tree;
  
  void init(int _n) {
    while(n < _n) {
      n *= 2;
    }
    tree.resize(2*n, zero);
  }

  void push(int pos) {
    if(pos < n) {
      tree[2*pos] = tree[2*pos].intersection(tree[pos]);
      tree[2*pos+1] = tree[2*pos+1].intersection(tree[pos]);
      tree[pos] = zero;
    }
  }
  
  void fullPush() {
    for(int loop = 1; loop < n; ++loop) {
      push(loop);
    }
  }

  void modif(inter value, inter zoneModif, int pos, inter nodeInter) {
    push(pos);
    if(zoneModif.contain(nodeInter)) {
      tree[pos] = tree[pos].intersection(value);
    }
    else {
      if(zoneModif.intersect(nodeInter.left())) {
        modif(value, zoneModif, pos*2, nodeInter.left());
      }
      if(zoneModif.intersect(nodeInter.right())) {
        modif(value, zoneModif, pos*2+1, nodeInter.right());
      }
    }
  }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  SegTree tree;
  tree.init(n);
  inter mod[k], modInter[k];
  for(int loop = 0; loop < k; ++loop) {
    if(op[loop] == 1) {
      mod[loop] = {height[loop], int(1e9)};
    }
    else {
      mod[loop] = {0, height[loop]};
    }
    modInter[loop] = {left[loop], right[loop]};
  }

  for(int loop = 0; loop < k; ++loop) {
    tree.modif(mod[loop], modInter[loop], 1, {0, tree.n - 1});
  }
  tree.fullPush();

  for(int loop = 0; loop < n; ++loop) {
    finalHeight[loop] = tree.tree[loop+tree.n].deb;
  }
}

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