oj.uz

Submission #1010356

# Submission time Handle Problem Language Result Execution time Memory
1010356 2024-06-28T22:23:14 Z somefjord Wall (IOI14_wall) C++17
0 / 100
 3000 ms 63188 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

constexpr int N = 1 << 21;
constexpr int INF = 1e9;

struct SegTree {
  vector<int> segmin;
  vector<int> segmax;
  vector<int> seg;
  int n;
  SegTree(int n) : segmin(2 * N, -1), segmax(2 * N, -1), seg(2 * N), n(n) {
    // fill_n(segmin.begin() + n, n, 0);
    // fill_n(segmax.begin(), n, INF);
  }

  void update(int l, int r, int h, int op) {
    l += n;
    r += n;
    while (r > l) {
      if (l & 1) {
        push(l);
        if (op == 1)
          segmin[l] = h;
        else
          segmax[l] = h;
        l++;
      }
      if (r & 1) {
        r--;
        push(r);
        if (op == 1)
          segmin[r] = h;
        else
          segmax[r] = h;
      }

      l /= 2;
      r /= 2;
    }

#ifdef DEBUG
    printf("%s [%d, %d): %d\n", op == 1 ? "ADD" : "REMOVE", l, r, h);
    print();
#endif
  }

  int query(int i) {
    i += n;
    return seg[i];
  }

  void propagate() {
    for (int i = 1; i < 2 * n; ++i) {
      push(i);
    }
  }

  void push(int u) {
    if (u >= n) {
      // leaf
      if (segmin[u] != -1) {
        seg[u] = max(segmin[u], seg[u]);
        segmin[u] = -1;
      }
      if (segmax[u] != -1) {
        seg[u] = min(segmax[u], seg[u]);
        segmax[u] = -1;
      }

      return;
    }

    if (segmin[u] != -1) {
      if (segmin[u * 2] != -1) {
        push(u * 2);
      }
      if (segmin[u * 2 + 1] != -1) {
        push(u * 2 + 1);
      }

      segmin[u * 2] = segmin[u];
      segmin[u * 2 + 1] = segmin[u];

      segmin[u] = -1;
    }

    if (segmax[u] != -1) {
      if (segmax[u * 2] != -1) {
        push(u * 2);
      }
      if (segmax[u * 2 + 1] != -1) {
        push(u * 2 + 1);
      }

      segmax[u * 2] = segmax[u];
      segmax[u * 2 + 1] = segmax[u];

      segmax[u] = -1;
    }
  }

  void print() {
    propagate();

    printf("--TREE--\n");
    int stop = 1;
    int layer = 1;
    for (int i = 1; i < 2 * n; ++i) {
      printf("[%d, %d] ", segmin[i], segmax[i]);
      if (i == stop) {
        printf("\n");
        stop += (layer *= 2);
      }
    }

    printf("\n--LEAF--\n");
    for (int i = 0; i < n; ++i) {
      printf("%d ", query(i));
    }
    printf("\n\n\n");
  }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[],
               int finalHeight[]) {
  SegTree tr(n);

  for (int i = 0; i < k; ++i) {
    tr.update(left[i], right[i] + 1, height[i], op[i]);
  }

  tr.propagate();
  for (int i = 0; i < n; ++i) {
    finalHeight[i] = tr.query(i);
  }

  return;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 49756 KB Output is correct
2 Correct 22 ms 49756 KB Output is correct
3 Incorrect 23 ms 49496 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 49500 KB Output is correct
2 Correct 107 ms 63188 KB Output is correct
3 Execution timed out 3019 ms 56656 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 49500 KB Output is correct
2 Correct 22 ms 49744 KB Output is correct
3 Incorrect 27 ms 49824 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 49500 KB Output is correct
2 Correct 22 ms 49676 KB Output is correct
3 Incorrect 23 ms 49492 KB Output isn't correct
4 Halted 0 ms 0 KB -