oj.uz

Submission #471436

# Submission time Handle Problem Language Result Execution time Memory
471436 2021-09-09T08:13:07 Z ashen_witch Wall (IOI14_wall) C++17
100 / 100
 1438 ms 85956 KB 
#include "bits/stdc++.h"
#include "wall.h"
 
using namespace std;
 
template <class T, class U, int SIZE>
struct LazySegTree {

  static_assert(__builtin_popcount(SIZE) == 1);

  const T kOpId = 0;
  const U kLazyId_1 = -1, kLazyId_2 = 1 << 17;

  T Op(T a, T b) {
    return max(a, b);
  }

  T tree[2 * SIZE];
  U lazy_1[2 * SIZE], lazy_2[2 * SIZE];

  LazySegTree() {
    for (int i = 0; i < 2 * SIZE; ++i)
      tree[i] = kOpId, lazy_1[i] = kLazyId_1, lazy_2[i] = kLazyId_2;
  }

  void Push(int cur, int low, int high) {
    int mid = (low + high) / 2;
    if (lazy_1[cur] != kLazyId_1) {
      Max(low, high, lazy_1[cur], 2 * cur, low, mid),
      Max(low, high, lazy_1[cur], 2 * cur + 1, mid + 1, high);
      lazy_1[cur] = kLazyId_1;
    }
    if (lazy_2[cur] != kLazyId_2) {
      Min(low, high, lazy_2[cur], 2 * cur, low, mid),
      Min(low, high, lazy_2[cur], 2 * cur + 1, mid + 1, high);
      lazy_2[cur] = kLazyId_2;
    }
  }

  void Pull(int cur) {
    tree[cur] = Op(tree[2 * cur], tree[2 * cur + 1]);
  }

  void Max(int l, int r, U val, int cur = 1, int low = 0, int high = SIZE - 1) {
    if (r < low || high < l)
      return;
    if (l <= low && high <= r) {
      tree[cur] = max(tree[cur], val);
      if (val > lazy_2[cur])
        lazy_1[cur] = lazy_2[cur] = val;
      else
        lazy_1[cur] = max(lazy_1[cur], val);
      return;
    }
    Push(cur, low, high);
    int mid = (low + high) / 2;
    Max(l, r, val, 2 * cur, low, mid),
    Max(l, r, val, 2 * cur + 1, mid + 1, high);
    Pull(cur);
  }

  void Min(int l, int r, U val, int cur = 1, int low = 0, int high = SIZE - 1) {
    if (r < low || high < l)
      return;
    if (l <= low && high <= r) {
      tree[cur] = min(tree[cur], val);
      lazy_2[cur] = min(lazy_2[cur], val);
      return;
    }
    Push(cur, low, high);
    int mid = (low + high) / 2;
    Min(l, r, val, 2 * cur, low, mid),
        Min(l, r, val, 2 * cur + 1, mid + 1, high);
    Pull(cur);
  }

  T Qry(int l, int r, int cur = 1, int low = 0, int high = SIZE - 1) {
    if (r < low || high < l)
      return kOpId;
    if (l <= low && high <= r)
      return tree[cur];
    Push(cur, low, high);
    int mid = (low + high) / 2;
    return Op(
        Qry(l, r, 2 * cur, low, mid),
        Qry(l, r, 2 * cur + 1, mid + 1, high)
    );
  }

};
 
const int kSize = 1 << 21;
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
  LazySegTree<int, int, kSize> tree;
  for (int i = 0; i < k; ++i) {
    if (op[i] == 1)
      tree.Max(left[i], right[i], height[i]);
    else
      tree.Min(left[i], right[i], height[i]);
  }
  for (int i = 0; i < n; ++i)
    finalHeight[i] = tree.Qry(i, i);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 49484 KB Output is correct
2 Correct 31 ms 49556 KB Output is correct
3 Correct 32 ms 49516 KB Output is correct
4 Correct 38 ms 49668 KB Output is correct
5 Correct 41 ms 49640 KB Output is correct
6 Correct 35 ms 49640 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 49528 KB Output is correct
2 Correct 405 ms 57336 KB Output is correct
3 Correct 287 ms 52840 KB Output is correct
4 Correct 838 ms 57880 KB Output is correct
5 Correct 431 ms 58400 KB Output is correct
6 Correct 462 ms 58392 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 49516 KB Output is correct
2 Correct 32 ms 49612 KB Output is correct
3 Correct 35 ms 49564 KB Output is correct
4 Correct 39 ms 49636 KB Output is correct
5 Correct 36 ms 49648 KB Output is correct
6 Correct 35 ms 49648 KB Output is correct
7 Correct 28 ms 49536 KB Output is correct
8 Correct 509 ms 57368 KB Output is correct
9 Correct 322 ms 52844 KB Output is correct
10 Correct 733 ms 57976 KB Output is correct
11 Correct 399 ms 58436 KB Output is correct
12 Correct 407 ms 58396 KB Output is correct
13 Correct 27 ms 49484 KB Output is correct
14 Correct 398 ms 57356 KB Output is correct
15 Correct 102 ms 50080 KB Output is correct
16 Correct 1060 ms 58148 KB Output is correct
17 Correct 446 ms 67212 KB Output is correct
18 Correct 423 ms 67184 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 49420 KB Output is correct
2 Correct 32 ms 49524 KB Output is correct
3 Correct 32 ms 49580 KB Output is correct
4 Correct 40 ms 49636 KB Output is correct
5 Correct 35 ms 49652 KB Output is correct
6 Correct 36 ms 49620 KB Output is correct
7 Correct 28 ms 49484 KB Output is correct
8 Correct 437 ms 57364 KB Output is correct
9 Correct 315 ms 52804 KB Output is correct
10 Correct 751 ms 57876 KB Output is correct
11 Correct 410 ms 58372 KB Output is correct
12 Correct 403 ms 58392 KB Output is correct
13 Correct 28 ms 49432 KB Output is correct
14 Correct 406 ms 57444 KB Output is correct
15 Correct 94 ms 50044 KB Output is correct
16 Correct 994 ms 58136 KB Output is correct
17 Correct 418 ms 67188 KB Output is correct
18 Correct 425 ms 67204 KB Output is correct
19 Correct 1345 ms 85928 KB Output is correct
20 Correct 1313 ms 83444 KB Output is correct
21 Correct 1337 ms 85956 KB Output is correct
22 Correct 1411 ms 83620 KB Output is correct
23 Correct 1311 ms 83340 KB Output is correct
24 Correct 1373 ms 83400 KB Output is correct
25 Correct 1296 ms 83340 KB Output is correct
26 Correct 1438 ms 85932 KB Output is correct
27 Correct 1332 ms 85872 KB Output is correct
28 Correct 1332 ms 83464 KB Output is correct
29 Correct 1301 ms 83460 KB Output is correct
30 Correct 1322 ms 83328 KB Output is correct