oj.uz

Submission #102766

# Submission time Handle Problem Language Result Execution time Memory
102766 2019-03-27T12:27:23 Z wxh010910 Wall (IOI14_wall) C++17
100 / 100
 1066 ms 57956 KB 
#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

const int inf = (int) 1e6;

class node {
 public:
  int l, r;

  node(int l = 0, int r = inf): l(l), r(r) {
  }

  void apply(const node &v) {
    int ll = v.l, rr = v.r;
    if (r < ll) {
      l = r = ll;
    } else if (l > rr) {
      l = r = rr;
    } else {
      l = max(l, ll);
      r = min(r, rr);
    }
  }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
  vector<node> tree(n * 2 - 1);
  function<void(int, int, int, int, int, node)> modify = [&](int x, int l, int r, int ll, int rr, node v) {
    if (ll <= l && r <= rr) {
      tree[x].apply(v);
    } else {
      int y = (l + r) >> 1, z = x + ((y - l + 1) << 1);
      tree[x + 1].apply(tree[x]);
      tree[z].apply(tree[x]);
      tree[x] = node();
      if (ll <= y) {
        modify(x + 1, l, y, ll, rr, v);
      }
      if (rr > y) {
        modify(z, y + 1, r, ll, rr, v);
      }
    }
  };
  function<void(int, int, int)> push = [&](int x, int l, int r) {
    if (l == r) {
      finalHeight[l] = tree[x].l;
    } else {
      int y = (l + r) >> 1, z = x + ((y - l + 1) << 1);
      tree[x + 1].apply(tree[x]);
      tree[z].apply(tree[x]);
      tree[x] = node();
      push(x + 1, l, y);
      push(z, y + 1, r);
    }
  };
  for (int i = 0; i < k; ++i) {
    if (op[i] == 1) {
      modify(0, 0, n - 1, left[i], right[i], node(height[i], inf));
    } else {
      modify(0, 0, n - 1, left[i], right[i], node(0, height[i]));
    }
  }
  push(0, 0, n - 1);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 10 ms 640 KB Output is correct
5 Correct 7 ms 640 KB Output is correct
6 Correct 12 ms 640 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 204 ms 8876 KB Output is correct
3 Correct 268 ms 4616 KB Output is correct
4 Correct 651 ms 10744 KB Output is correct
5 Correct 377 ms 10664 KB Output is correct
6 Correct 349 ms 10872 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 10 ms 660 KB Output is correct
5 Correct 9 ms 640 KB Output is correct
6 Correct 8 ms 640 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 153 ms 8924 KB Output is correct
9 Correct 211 ms 4516 KB Output is correct
10 Correct 714 ms 10768 KB Output is correct
11 Correct 337 ms 10756 KB Output is correct
12 Correct 364 ms 10744 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 156 ms 8824 KB Output is correct
15 Correct 40 ms 1656 KB Output is correct
16 Correct 849 ms 10860 KB Output is correct
17 Correct 476 ms 19136 KB Output is correct
18 Correct 389 ms 19260 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 13 ms 640 KB Output is correct
5 Correct 7 ms 640 KB Output is correct
6 Correct 8 ms 640 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 147 ms 8756 KB Output is correct
9 Correct 220 ms 4700 KB Output is correct
10 Correct 638 ms 10632 KB Output is correct
11 Correct 373 ms 10688 KB Output is correct
12 Correct 314 ms 10872 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 163 ms 8832 KB Output is correct
15 Correct 42 ms 1856 KB Output is correct
16 Correct 819 ms 10836 KB Output is correct
17 Correct 342 ms 19192 KB Output is correct
18 Correct 362 ms 19320 KB Output is correct
19 Correct 861 ms 57832 KB Output is correct
20 Correct 834 ms 57720 KB Output is correct
21 Correct 789 ms 57704 KB Output is correct
22 Correct 824 ms 57896 KB Output is correct
23 Correct 884 ms 57936 KB Output is correct
24 Correct 845 ms 57756 KB Output is correct
25 Correct 854 ms 57920 KB Output is correct
26 Correct 849 ms 57848 KB Output is correct
27 Correct 827 ms 57720 KB Output is correct
28 Correct 940 ms 57948 KB Output is correct
29 Correct 1066 ms 57956 KB Output is correct
30 Correct 1061 ms 57852 KB Output is correct