oj.uz

Submission #762644

# Submission time Handle Problem Language Result Execution time Memory
762644 2023-06-21T15:18:42 Z gun_gan Wall (IOI14_wall) C++17
100 / 100
 640 ms 92248 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) {
            // cout << "apply " << u << ' ' << v << '\n';

            // cout << lazyMax[u] << " " << lazyMin[u] << '\n'; 
            // cout << lazyMax[v] << " " << lazyMin[v] << '\n';

            if(lazyMax[u] <= lazyMax[v] && lazyMin[v] <= lazyMin[u]) {
                  lazyMax[u] = lazyMax[v];
                  lazyMin[u] = lazyMin[v];
            } else if(lazyMin[v] <= lazyMax[u]) {
                  lazyMax[u] = lazyMin[u] = lazyMin[v];
            } else if(lazyMin[u] <= lazyMax[v]) { 
                  lazyMax[u] = lazyMin[u] = lazyMax[v];
            } else if(lazyMax[u] < lazyMax[v] && lazyMax[v] <= lazyMin[u] && lazyMin[u] <= lazyMin[v]) {
                  lazyMax[u] = lazyMax[v];
            } else if(lazyMax[v] <= lazyMax[u] && lazyMax[u] <= lazyMin[v] && lazyMin[v] < lazyMin[u]) {
                  lazyMin[u] = lazyMin[v];
            } 
      }

      void push(int v, int l, int r) {
            if(l == r) return; 
            if(lazyMax[v] == 0 && lazyMin[v] == 1e9) 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);  
                  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) {
                  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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31592 KB Output is correct
2 Correct 16 ms 31692 KB Output is correct
3 Correct 16 ms 31572 KB Output is correct
4 Correct 20 ms 31952 KB Output is correct
5 Correct 18 ms 31956 KB Output is correct
6 Correct 18 ms 31948 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31572 KB Output is correct
2 Correct 129 ms 45260 KB Output is correct
3 Correct 202 ms 39184 KB Output is correct
4 Correct 553 ms 47692 KB Output is correct
5 Correct 248 ms 48740 KB Output is correct
6 Correct 236 ms 48152 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31572 KB Output is correct
2 Correct 17 ms 31748 KB Output is correct
3 Correct 14 ms 31572 KB Output is correct
4 Correct 22 ms 32124 KB Output is correct
5 Correct 17 ms 32028 KB Output is correct
6 Correct 17 ms 31964 KB Output is correct
7 Correct 14 ms 31572 KB Output is correct
8 Correct 125 ms 45180 KB Output is correct
9 Correct 197 ms 39084 KB Output is correct
10 Correct 543 ms 51032 KB Output is correct
11 Correct 235 ms 52044 KB Output is correct
12 Correct 231 ms 50484 KB Output is correct
13 Correct 12 ms 31572 KB Output is correct
14 Correct 128 ms 45252 KB Output is correct
15 Correct 45 ms 33056 KB Output is correct
16 Correct 640 ms 51228 KB Output is correct
17 Correct 249 ms 50676 KB Output is correct
18 Correct 245 ms 50784 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31572 KB Output is correct
2 Correct 13 ms 31744 KB Output is correct
3 Correct 14 ms 31672 KB Output is correct
4 Correct 19 ms 32040 KB Output is correct
5 Correct 17 ms 32004 KB Output is correct
6 Correct 18 ms 32000 KB Output is correct
7 Correct 14 ms 31524 KB Output is correct
8 Correct 124 ms 45264 KB Output is correct
9 Correct 202 ms 39100 KB Output is correct
10 Correct 542 ms 50976 KB Output is correct
11 Correct 242 ms 52152 KB Output is correct
12 Correct 232 ms 50440 KB Output is correct
13 Correct 13 ms 31572 KB Output is correct
14 Correct 128 ms 45264 KB Output is correct
15 Correct 50 ms 33144 KB Output is correct
16 Correct 637 ms 51304 KB Output is correct
17 Correct 248 ms 50764 KB Output is correct
18 Correct 241 ms 50660 KB Output is correct
19 Correct 588 ms 92232 KB Output is correct
20 Correct 590 ms 89748 KB Output is correct
21 Correct 590 ms 92164 KB Output is correct
22 Correct 586 ms 89680 KB Output is correct
23 Correct 580 ms 89784 KB Output is correct
24 Correct 583 ms 89732 KB Output is correct
25 Correct 581 ms 89696 KB Output is correct
26 Correct 597 ms 92236 KB Output is correct
27 Correct 591 ms 92248 KB Output is correct
28 Correct 585 ms 89720 KB Output is correct
29 Correct 582 ms 89648 KB Output is correct
30 Correct 585 ms 89684 KB Output is correct