oj.uz

답안 #59021

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
59021 2018-07-20T08:14:41 Z ruhanhabib39 벽 (IOI14_wall) C++17
8 / 100
 3000 ms 50992 KB 
#include "wall.h"
#include <algorithm>
#include <cstdio>
#include <cassert>

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

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

   Range tree[4 * MAXN + 10];
   
   void init(int cn, int b, int e) {
      tree[cn] = {0, 0, 1};
      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) {
      if(r < b || l > e) return;
      int m = (b + e) / 2;
      if(b != e && tree[cn].pos_left != -1) {
         upd(2*cn, b, m, b, m, tree[cn]);
         upd(2*cn+1, m+1, e, m+1, e, tree[cn]);
      }
      //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;
      }
      upd(2*cn, b, m, l, r, rng);
      upd(2*cn+1, m+1, e, l, r, rng);
      tree[cn] = Range{0, INF, -1};
   }

   void get_res(int cn, int b, int e, Range rng, int finalHeight[]) {
      if(b == e) {
         Range res_range = tree[cn].inters(rng);
         if(res_range.pos_left == 1) finalHeight[b] = res_range.l;
         else finalHeight[b] = res_range.r;
         if(finalHeight[b] == INF) finalHeight[b] = 0;
         //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;
      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);
   tree[0] = Range{0, 0, 1};
   for(int i = 0; i < k; i++) {
      Range rng;
      if(op[i] == 1) rng = Range{height[i], INF, 1};
      else rng = Range{0, height[i], 0};
      for(int j = left[i]; j <= right[i]; j++) {
         tree[j] = tree[j].inters(rng);
      }
      //if(op[i] == 1) upd(1, 0, n-1, left[i], right[i], Range{height[i], INF, 1});
      //else upd(1, 0, n-1, left[i], right[i], Range{0, height[i], 0});
   }
   //get_res(1, 0, n-1, Range{0, INF, -1}, finalHeight);
   for(int i = 0; i < n; i++) {
      if(tree[i].pos_left) finalHeight[i] = tree[i].l;
      else finalHeight[i] = tree[i].r;
   }
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 7 ms 616 KB Output is correct
3 Correct 4 ms 616 KB Output is correct
4 Correct 46 ms 1176 KB Output is correct
5 Correct 36 ms 1212 KB Output is correct
6 Correct 63 ms 1444 KB Output is correct

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1444 KB Output is correct
2 Correct 232 ms 14636 KB Output is correct
3 Execution timed out 3031 ms 14720 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14720 KB Output is correct
2 Correct 6 ms 14720 KB Output is correct
3 Correct 4 ms 14720 KB Output is correct
4 Correct 49 ms 14720 KB Output is correct
5 Correct 58 ms 14720 KB Output is correct
6 Correct 54 ms 14720 KB Output is correct
7 Correct 3 ms 14720 KB Output is correct
8 Correct 183 ms 24556 KB Output is correct
9 Execution timed out 3046 ms 24664 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 24664 KB Output is correct
2 Correct 6 ms 24664 KB Output is correct
3 Correct 4 ms 24664 KB Output is correct
4 Correct 39 ms 24664 KB Output is correct
5 Correct 43 ms 24664 KB Output is correct
6 Correct 57 ms 24664 KB Output is correct
7 Correct 3 ms 24664 KB Output is correct
8 Correct 181 ms 34492 KB Output is correct
9 Correct 2801 ms 34664 KB Output is correct
10 Execution timed out 3060 ms 50992 KB Time limit exceeded
11 Halted 0 ms 0 KB -