제출 #59221

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59221		ruhanhabib39	벽 (IOI14_wall)	C++17	100 / 100	1102 ms	154772 KiB

wall

#include "wall.h"
#include <algorithm>
#include <cstdio>
#include <cassert>

namespace {
   const int MAXN = 2e6;
   const int INF = 1e9;

   struct Range {
      int l, r;
      bool operator==(Range rng) const {
         return l == rng.l && r == rng.r;
      }
      bool operator!=(Range rng) const {
         return l != rng.l || r != rng.r;
      }
      Range inters(Range rng) const {
         if(r < rng.l) {
            return Range{rng.l, rng.l};
         }
         if(rng.r < l) {
            return Range{rng.r, rng.r};
         }
         auto res = Range{std::max(l, rng.l), std::min(r, rng.r)};
         return res;
      }
   };

   Range tree[4 * MAXN + 10];
   
   void init(int cn, int b, int e) {
      tree[cn] = {0, 0};
      if(b == e) return;
      int m = (b + e) / 2;
      init(2*cn, b, m);
      init(2*cn+1, m+1, e);
   }

   void upd(int cn, int b, int e, int l, int r, Range rng, Range prop = Range{0, INF}) {
      //fprintf(stderr, "before prop tree[%d,%d] = {[%d,%d], %d}\n", b, e, tree[cn].l, tree[cn].r, tree[cn].pos_left);
      tree[cn] = tree[cn].inters(prop);
      //fprintf(stderr, "after prop tree[%d,%d] = {[%d,%d], %d}\n", b, e, tree[cn].l, tree[cn].r, tree[cn].pos_left);

      if(r < b || l > e) return;
      int m = (b + e) / 2;
      //fprintf(stderr, "upd([%d,%d],[%d,%d],[%d,%d]\n", b, e, l, r, rng.l, rng.r);
      if(l <= b && e <= r) {
         //fprintf(stderr, "before tree[%d,%d] = {[%d,%d],%d}\n", b, e, tree[cn].l, tree[cn].r, tree[cn].pos_left);
         tree[cn] = tree[cn].inters(rng);
         //fprintf(stderr, "after tree[%d,%d] = {[%d,%d],%d}\n", b, e, tree[cn].l, tree[cn].r, tree[cn].pos_left);
         return;
      }
      prop = tree[cn];
      upd(2*cn, b, m, l, r, rng, prop);
      upd(2*cn+1, m+1, e, l, r, rng, prop);
      tree[cn] = Range{0, INF};
   }

   void get_res(int cn, int b, int e, Range rng, int finalHeight[]) {
      if(b == e) {
         Range res_range = tree[cn].inters(rng);
         finalHeight[b] = res_range.l;
         //fprintf(stderr, "pos_left[%d] = %d, val = %d, range = [%d, %d]\n", b, rng.pos_left, finalHeight[b], res_range.l, res_range.r);
         return;
      }
      int m = (b + e) / 2;
      rng = tree[cn].inters(rng);
      get_res(2*cn, b, m, tree[cn].inters(rng), finalHeight);
      get_res(2*cn+1, m+1, e, tree[cn].inters(rng), finalHeight);
   }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
   init(1, 0, n-1);
   for(int i = 0; i < k; i++) {
      Range rng;
      if(op[i] == 1) rng = Range{height[i], INF};
      else rng = Range{0, height[i]};
      upd(1, 0, n-1, left[i], right[i], rng);
   }
   get_res(1, 0, n-1, Range{0, INF}, finalHeight);
}

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