oj.uz

Submission #997779

# Submission time Handle Problem Language Result Execution time Memory
997779 2024-06-12T20:19:47 Z coolboy19521 Wall (IOI14_wall) C++17
100 / 100
 1002 ms 262144 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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 235092 KB Output is correct
2 Correct 89 ms 235096 KB Output is correct
3 Correct 90 ms 235088 KB Output is correct
4 Correct 94 ms 235344 KB Output is correct
5 Correct 96 ms 235348 KB Output is correct
6 Correct 93 ms 235344 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 235088 KB Output is correct
2 Correct 238 ms 242916 KB Output is correct
3 Correct 245 ms 238448 KB Output is correct
4 Correct 600 ms 243536 KB Output is correct
5 Correct 363 ms 244048 KB Output is correct
6 Correct 310 ms 244052 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 235084 KB Output is correct
2 Correct 93 ms 235204 KB Output is correct
3 Correct 90 ms 235092 KB Output is correct
4 Correct 95 ms 235348 KB Output is correct
5 Correct 93 ms 235320 KB Output is correct
6 Correct 127 ms 235624 KB Output is correct
7 Correct 89 ms 235088 KB Output is correct
8 Correct 172 ms 248912 KB Output is correct
9 Correct 254 ms 242720 KB Output is correct
10 Correct 606 ms 253264 KB Output is correct
11 Correct 319 ms 254288 KB Output is correct
12 Correct 321 ms 252756 KB Output is correct
13 Correct 92 ms 235000 KB Output is correct
14 Correct 174 ms 248912 KB Output is correct
15 Correct 122 ms 236292 KB Output is correct
16 Correct 726 ms 253320 KB Output is correct
17 Correct 323 ms 252876 KB Output is correct
18 Correct 332 ms 252896 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 235092 KB Output is correct
2 Correct 107 ms 235088 KB Output is correct
3 Correct 83 ms 235088 KB Output is correct
4 Correct 108 ms 235392 KB Output is correct
5 Correct 97 ms 235376 KB Output is correct
6 Correct 111 ms 235344 KB Output is correct
7 Correct 107 ms 235092 KB Output is correct
8 Correct 187 ms 248652 KB Output is correct
9 Correct 247 ms 242232 KB Output is correct
10 Correct 612 ms 253216 KB Output is correct
11 Correct 373 ms 254288 KB Output is correct
12 Correct 313 ms 252756 KB Output is correct
13 Correct 89 ms 235088 KB Output is correct
14 Correct 175 ms 248660 KB Output is correct
15 Correct 123 ms 236252 KB Output is correct
16 Correct 710 ms 253472 KB Output is correct
17 Correct 308 ms 252752 KB Output is correct
18 Correct 345 ms 252784 KB Output is correct
19 Correct 976 ms 262144 KB Output is correct
20 Correct 948 ms 262144 KB Output is correct
21 Correct 954 ms 262144 KB Output is correct
22 Correct 954 ms 262144 KB Output is correct
23 Correct 962 ms 262144 KB Output is correct
24 Correct 938 ms 262144 KB Output is correct
25 Correct 932 ms 262144 KB Output is correct
26 Correct 965 ms 262144 KB Output is correct
27 Correct 905 ms 262144 KB Output is correct
28 Correct 1002 ms 262144 KB Output is correct
29 Correct 927 ms 262144 KB Output is correct
30 Correct 948 ms 262144 KB Output is correct