oj.uz

Submission #762623

# Submission time Handle Problem Language Result Execution time Memory
762623 2023-06-21T14:50:53 Z gun_gan Wall (IOI14_wall) C++17
24 / 100
 542 ms 51640 KB 
#include <bits/stdc++.h>
using namespace std;

const int MX = 2e6 + 5;

struct segtree {
      int lazyMin[4 * MX], lazyMax[4 * MX], res[MX];

      // each range [l, r] consider we have a bound such that elements are
      // in [lazyMax, lazyMin], treat max updates as increase in lower bound
      // treat min updates as decrease in upper bound
      // when lazyMax = lazyMin, updates becomes equivalent to range set

      void apply(int u, int v) {
            if(lazyMax[u] <= lazyMax[v] && lazyMin[u] >= lazyMin[v]) {
                  lazyMax[u] = lazyMax[v];
                  lazyMin[u] = lazyMin[v];
            } else if(lazyMin[v] <= lazyMax[u]) {
                  lazyMax[u] = lazyMin[u] = lazyMin[v];
            } else if(lazyMax[v] >= lazyMin[u]) { 
                  lazyMax[u] = lazyMin[u] = lazyMax[v];
            }
      }

      void push(int v, int l, int r) {
            if(l == r) return;      
            
            apply(v * 2 + 0, v);
            apply(v * 2 + 1, v);

            assert(lazyMax[2 * v] <= lazyMin[2 * v]);
            assert(lazyMax[2 * v + 1] <= lazyMin[2 * v + 1]);

            lazyMax[v] = 0, lazyMin[v] = 1e9;
      }

      void minimize(int v, int l, int r, int ql, int qr, int x) {
            push(v, l, r);
            if(r < ql || l > qr) return;
            if(ql <= l && qr >= r) {
                  if(lazyMax[v] > x) {
                        lazyMax[v] = lazyMin[v] = x;
                  } else if(lazyMin[v] > x) {
                        lazyMin[v] = x;
                  }
                  push(v, l, r);
                  // cout << "minim (" << l << "," << r << ") " << lazyMin[v] << ' ' << lazyMax[v] << " " << v << '\n';  
                  return;
            }
            int m = (l + r) >> 1;
            minimize(v * 2 + 0, l, m + 0, ql, qr, x);
            minimize(v * 2 + 1, m + 1, r, ql, qr, x);
      }

      void maximize(int v, int l, int r, int ql, int qr, int x) {
            push(v, l, r);
            if(r < ql || l > qr) return;
            if(ql <= l && qr >= r) {
                  if(lazyMin[v] < x) {
                        lazyMax[v] = lazyMin[v] = x;
                  } else if(lazyMax[v] < x) {
                        lazyMax[v] = x;
                  }
                  push(v, l, r);
                  return;
            }
            

            int m = (l + r) >> 1;
            maximize(v * 2 + 0, l, m + 0, ql, qr, x);
            maximize(v * 2 + 1, m + 1, r, ql, qr, x);
      }

      void get(int v, int l, int r) {
            push(v, l, r);
            if(l == r) {
                  // cout << "get (" << l << "," << r << ") " << lazyMax[v] << " " << lazyMin[v] << " " << v << '\n';
                  res[l] = min(lazyMax[v], lazyMin[v]);
                  return;
            }

            int m = (l + r) >> 1;
            get(v * 2 + 0, l, m + 0);
            get(v * 2 + 1, m + 1, r);
      }

      void init() {
            for(int i = 0; i < 4 * MX; i++) {
                  lazyMin[i] = 1e9;
            }
      }
} st;

void buildWall(int N, int K, int op[], int l[], int r[], int h[], int finalHeight[]) {
      st.init();

      for(int i = 0; i < K; i++) {
            if(op[i] == 1) st.maximize(1, 0, N - 1, l[i], r[i], h[i]);
            else st.minimize(1, 0, N - 1, l[i], r[i], h[i]);
      }

      st.get(1, 0, N - 1);
      for(int i = 0; i < N; i++) {
            finalHeight[i] = st.res[i];
      }
}

// int op[100], l[100], r[100], h[100], N, K, f[100];

// int main() {
//       cin >> N >> K;
//       for(int i = 0; i < K; i++) {
//             cin >> op[i] >> l[i] >> r[i] >> h[i];
//       }

//       buildWall(N, K, op, l, r, h, f);
// }

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31572 KB Output is correct
2 Correct 14 ms 31708 KB Output is correct
3 Incorrect 15 ms 31680 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 13 ms 31612 KB Output is correct
2 Correct 135 ms 45248 KB Output is correct
3 Correct 197 ms 39072 KB Output is correct
4 Correct 542 ms 50976 KB Output is correct
5 Correct 263 ms 51640 KB Output is correct
6 Correct 268 ms 50472 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31572 KB Output is correct
2 Correct 14 ms 31700 KB Output is correct
3 Incorrect 14 ms 31620 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31620 KB Output is correct
2 Correct 14 ms 31700 KB Output is correct
3 Incorrect 15 ms 31576 KB Output isn't correct
4 Halted 0 ms 0 KB -