oj.uz

Submission #997780

# Submission time Handle Problem Language Result Execution time Memory
997780 2024-06-12T20:21:41 Z coolboy19521 Wall (IOI14_wall) C++17
24 / 100
 638 ms 244052 KB 
#include "bits/stdc++.h"
#include "wall.h"

using namespace std;

const int sz = 5e6;

struct que {
  int ad, rm;
  que() : ad(INT_MIN), rm(INT_MAX) {}
  que(int le, int ri) : ad(le), rm(ri) {}
};

int st[sz * 4];
que lz[sz * 4];

void merge(que& le, que& ri) {
  // le.ad = max(le.ad, ri.ad);
  // le.rm = min(le.rm, ri.rm);
  // le.ad = min(le.ad, le.rm);
  le.rm = min(le.rm, ri.rm);
  // le.rm = max(le.rm, ri.ad);
  le.ad = max(le.ad, ri.ad);
  le.ad = min(le.ad, ri.rm);
}

void relax(int v, int le, int ri) {
  if (lz[v].ad != INT_MIN || lz[v].rm != INT_MAX) {
    if (lz[v].ad != INT_MIN) {
      st[v] = max(st[v], lz[v].ad);
    }
    if (lz[v].rm != INT_MAX) {
      st[v] = min(st[v], lz[v].rm);
    }
    if (le != ri) {
      merge(lz[v * 2], lz[v]);
      merge(lz[v * 2 + 1], lz[v]);
    }
    lz[v] = que();
  }
}

void update(int le, int ri, int ql, int qr, int v, que q) {
  relax(v, le, ri);
  if (le > qr || ri < ql) return;
  if (ql <= le && ri <= qr) {
    merge(lz[v], q);
    relax(v, le, ri);
  } else {
    int mi = le + (ri - le) / 2;
    update(le, mi, ql, qr, v * 2, q);
    update(mi + 1, ri, ql, qr, v * 2 + 1, q);
    st[v] = min(st[v * 2], st[v * 2 + 1]);
  }
}

int query(int le, int ri, int ix, int v) {
  relax(v, le, ri);
  if (le > ix || ri < ix) return 0;
  if (le == ri) return st[v];
  int mi = le + (ri - le) / 2;
  // if (ix <= mi) return query(le, mi, ix, v * 2);
  int lq = query(le, mi, ix, v * 2);
  int rq = query(mi + 1, ri, ix, v * 2 + 1);
  return lq + rq;
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
  fill(st, st + sz * 4, 0);
  fill(lz, lz + sz * 4, que());
  
  for (int i = 0; i < k; i++) {
    if (1 == op[i]) {
      que q = {height[i], INT_MAX};
      update(1, n, left[i] + 1, right[i] + 1, 1, q);
    } else {
      que q = {INT_MIN, height[i]};
      update(1, n, left[i] + 1, right[i] + 1, 1, q);
    }
  }

  for (int i = 0; i < n; i++) {
    finalHeight[i] = query(1, n, i + 1, 1);
  }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 235088 KB Output is correct
2 Correct 82 ms 235088 KB Output is correct
3 Incorrect 92 ms 235092 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 235088 KB Output is correct
2 Correct 185 ms 243032 KB Output is correct
3 Correct 239 ms 238496 KB Output is correct
4 Correct 638 ms 243540 KB Output is correct
5 Correct 307 ms 244024 KB Output is correct
6 Correct 311 ms 244052 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 235092 KB Output is correct
2 Correct 90 ms 235284 KB Output is correct
3 Incorrect 90 ms 235236 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 235224 KB Output is correct
2 Correct 92 ms 235144 KB Output is correct
3 Incorrect 84 ms 235088 KB Output isn't correct
4 Halted 0 ms 0 KB -