oj.uz

Submission #59221

# Submission time Handle Problem Language Result Execution time Memory
59221 2018-07-21T08:33:11 Z ruhanhabib39 Wall (IOI14_wall) C++17
100 / 100
 1102 ms 154772 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 5 ms 420 KB Output is correct
4 Correct 10 ms 880 KB Output is correct
5 Correct 10 ms 956 KB Output is correct
6 Correct 9 ms 1016 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1016 KB Output is correct
2 Correct 196 ms 8488 KB Output is correct
3 Correct 215 ms 8488 KB Output is correct
4 Correct 753 ms 20788 KB Output is correct
5 Correct 460 ms 31372 KB Output is correct
6 Correct 442 ms 39992 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 39992 KB Output is correct
2 Correct 5 ms 39992 KB Output is correct
3 Correct 4 ms 39992 KB Output is correct
4 Correct 10 ms 39992 KB Output is correct
5 Correct 10 ms 39992 KB Output is correct
6 Correct 12 ms 39992 KB Output is correct
7 Correct 3 ms 39992 KB Output is correct
8 Correct 200 ms 39992 KB Output is correct
9 Correct 233 ms 39992 KB Output is correct
10 Correct 743 ms 49124 KB Output is correct
11 Correct 451 ms 59744 KB Output is correct
12 Correct 460 ms 68368 KB Output is correct
13 Correct 3 ms 68368 KB Output is correct
14 Correct 256 ms 70960 KB Output is correct
15 Correct 55 ms 70960 KB Output is correct
16 Correct 931 ms 76180 KB Output is correct
17 Correct 418 ms 76180 KB Output is correct
18 Correct 439 ms 76180 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 76180 KB Output is correct
2 Correct 4 ms 76180 KB Output is correct
3 Correct 5 ms 76180 KB Output is correct
4 Correct 9 ms 76180 KB Output is correct
5 Correct 8 ms 76180 KB Output is correct
6 Correct 13 ms 76180 KB Output is correct
7 Correct 2 ms 76180 KB Output is correct
8 Correct 248 ms 76180 KB Output is correct
9 Correct 281 ms 76180 KB Output is correct
10 Correct 773 ms 76180 KB Output is correct
11 Correct 460 ms 76432 KB Output is correct
12 Correct 483 ms 76432 KB Output is correct
13 Correct 3 ms 76432 KB Output is correct
14 Correct 193 ms 76432 KB Output is correct
15 Correct 61 ms 76432 KB Output is correct
16 Correct 911 ms 76848 KB Output is correct
17 Correct 565 ms 77092 KB Output is correct
18 Correct 413 ms 77092 KB Output is correct
19 Correct 929 ms 124736 KB Output is correct
20 Correct 960 ms 124736 KB Output is correct
21 Correct 1072 ms 124868 KB Output is correct
22 Correct 1078 ms 132892 KB Output is correct
23 Correct 1102 ms 143268 KB Output is correct
24 Correct 1085 ms 152400 KB Output is correct
25 Correct 1085 ms 152400 KB Output is correct
26 Correct 927 ms 154772 KB Output is correct
27 Correct 913 ms 154772 KB Output is correct
28 Correct 955 ms 154772 KB Output is correct
29 Correct 986 ms 154772 KB Output is correct
30 Correct 983 ms 154772 KB Output is correct