oj.uz

Submission #889507

# Submission time Handle Problem Language Result Execution time Memory
889507 2023-12-19T20:48:38 Z uped Wall (IOI14_wall) C++17
0 / 100
 515 ms 21216 KB 
#include "wall.h"

#include <bits/stdc++.h>

using namespace std;

#define DEBUG(a) cout << #a << ": " << a << '\n';

using ll = long long;

struct lazy_segtree {
    using T = int;
    using U = pair<int, int>;
    T value_identity = 0ll;
    U operation_identity = {INT32_MIN, INT32_MAX};
    U compose(U a, U b) {
        // if disjoint prefer right????
        if (a.second < b.first || b.second < a.first) {
          return b;
        }
        return {max(a.first, b.first), min(a.second, b.second)};
    }

    T apply(T a, U b, int n) {
        if (a < b.first) {
          return b.first;
        }
        if (a > b.second) {
          return b.second;
        }
        return a;
    }

    T combine(T a, T b) {
        return a + b;
    }

    int size;
    vector<T> tree;
    vector<U> operations;
    lazy_segtree(int n) {
        size = 1;
        while (size < n) size *= 2;
        tree.assign(2 * size, value_identity);
        operations.assign(2 * size, operation_identity);
    }

    void propagate(int x, int lx, int rx) {
        if (rx - lx == 1) {
            return;
        }

        int m = (lx + rx) / 2;
        operations[2 * x + 1] = compose(operations[2 * x + 1], operations[x]);
        operations[2 * x + 2] = compose(operations[2 * x + 2], operations[x]);
        tree[2 * x + 1] = apply(tree[2 * x + 1], operations[x], m - lx);
        tree[2 * x + 2] = apply(tree[2 * x + 2], operations[x], rx - m);
        operations[x] = operation_identity;
    }

    void modify(int l, int r, U v, int x, int lx, int rx) {
        propagate(x, lx, rx);
        if (lx >= r || rx <= l) return;
        if (l <= lx && rx <= r) {
            operations[x] = compose(operations[x], v);
            tree[x] = apply(tree[x], v, rx - lx);
            return;
        }
        int m = (lx + rx) / 2;
        modify(l, r, v, 2 * x + 1, lx, m);
        modify(l, r, v, 2 * x + 2, m, rx);
        tree[x] = combine(tree[2 * x + 1], tree[2 * x + 2]);
    }

    void modify(int l, int r, U v) {
        modify(l, r, v, 0, 0, size);
    }

    T query(int l, int r, int x, int lx, int rx) {
        propagate(x, lx, rx);
        if (lx >= r || rx <= l) return value_identity;
        if (l <= lx && rx <= r) {
            return tree[x];
        }
        int m = (lx + rx) / 2;
        T a = query(l, r, 2 * x + 1, lx, m);
        T b = query(l, r, 2 * x + 2, m, rx);
        return combine(a, b);
    }

    T query(int l, int r) {
      return query(l, r, 0, 0, size);  
    }

    T query(int i, int x, int lx, int rx) {
        propagate(x, lx, rx);
        if (rx - lx == 1) {
            return tree[x];
        }
        int m = (lx + rx) / 2;
        if (i < m) {
            return query(i, 2 * x + 1, lx, m);
        } else {
            return query(i, 2 * x + 2, m, rx);
        }
    }

    T query(int i) {
        return query(i, 0, 0, size);
    }

    void build(vector<T>& v, int x, int lx, int rx) {
        if (rx - lx == 1) {
            if (lx < v.size()) {
                tree[x] = v[lx];
            }
            return;
        }
        int m = (lx + rx) / 2;
        build(v, 2 * x + 1, lx, m);
        build(v, 2 * x + 2, m, rx);
        tree[x] = combine(tree[2 * x + 1], tree[2 * x + 2]);
    }

    void build(vector<T>& v) {
        build(v, 0, 0, size);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  lazy_segtree st(n);
  for (int i = 0; i < k; ++i) {
    if (op[i] == 1) {
      st.modify(left[i], right[i] + 1, {height[i], INT32_MAX});
    } else {
      st.modify(left[i], right[i] + 1, {INT32_MIN, height[i]});
    }
  }
  for (int i = 0; i < n; ++i) {
    finalHeight[i] = st.query(i);
  }

  return;
}

// int main() {
//   int n, k;
//   cin >> n >> k;
//   int op[100];
//   int left[100];
//   int right[100];
//   int height[100];
//   int finalHeight[100];
//   for (int i = 0; i < k; ++i) {
//     cin >> op[i] >> left[i] >> right[i] >> height[i];
//   }
//   buildWall(n, k, op, left, right, height, finalHeight);
//   for (int i = 0; i  < n; ++i) {
//     cout << finalHeight[i] << '\n';
//   }
// }

Compilation message

wall.cpp: In member function 'void lazy_segtree::build(std::vector<int>&, int, int, int)':
wall.cpp:114:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |             if (lx < v.size()) {
      |                 ~~~^~~~~~~~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 109 ms 14052 KB Output is correct
3 Correct 181 ms 8276 KB Output is correct
4 Incorrect 515 ms 21216 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 432 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Incorrect 2 ms 448 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

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