oj.uz

답안 #1062519

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1062519 2024-08-17T08:12:06 Z cloudy 벽 (IOI14_wall) C++17
24 / 100
 591 ms 14820 KB 
#include <bits/stdc++.h>
#define fastIO                      \
  ios_base::sync_with_stdio(false); \
  cin.tie(nullptr)
using namespace std;
#define ll long long
#define pii pair<ll, ll>
#define mp make_pair
#define f first
#define s second
#define pb push_back
const ll INF = 1000000000000000000;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
string stepDir = "URDL";

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  os << '{';
  string sep;
  for (const auto &x : v) os << sep << x, sep = ", ";
  return os << '}';
}
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
  return os << '(' << p.first << ", " << p.second << ')';
}
void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
  cerr << ' ' << H;
  dbg_out(T...);
}
#ifdef DEBUG
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
#define MOD 1000000007

struct segtree {
  int size;
  const ll NO_OP_MAX = LLONG_MIN;
  const ll NO_OP_MIN = LLONG_MAX;
  vector<ll> max_operations, min_operations, values;

  ll modify_op_max(ll a, ll b) {
    if (b == NO_OP_MAX) return a;
    return max(a, b);
  }

  ll modify_op_min(ll a, ll b) {
    if (b == NO_OP_MIN) return a;
    return min(a, b);
  }

  void apply_mod_op_max(ll &a, ll b) { a = modify_op_max(a, b); }

  void apply_mod_op_min(ll &a, ll b) { a = modify_op_min(a, b); }

  void init(int n) {
    size = 1;
    while (size < n) size *= 2;
    max_operations.assign(2 * size, NO_OP_MAX);
    min_operations.assign(2 * size, NO_OP_MIN);
    values.assign(2 * size, 0LL);
  }

  void propagate(int x, int lx, int rx) {
    if (rx - lx == 1) return;  // leaves
    int m = (lx + rx) / 2;

    apply_mod_op_max(max_operations[2 * x + 1], max_operations[x]);
    apply_mod_op_max(values[2 * x + 1], max_operations[x]);
    apply_mod_op_min(min_operations[2 * x + 1], min_operations[x]);
    apply_mod_op_min(values[2 * x + 1], min_operations[x]);

    apply_mod_op_max(max_operations[2 * x + 2], max_operations[x]);
    apply_mod_op_max(values[2 * x + 2], max_operations[x]);
    apply_mod_op_min(min_operations[2 * x + 2], min_operations[x]);
    apply_mod_op_min(values[2 * x + 2], min_operations[x]);

    max_operations[x] = NO_OP_MAX;
    min_operations[x] = NO_OP_MIN;
  }

  void op_max(int l, int r, ll v, int x, int lx, int rx) {
    propagate(x, lx, rx);
    if (lx >= r || rx <= l) return;
    if (lx >= l && rx <= r) {
      apply_mod_op_max(max_operations[x], v);
      apply_mod_op_max(values[x], v);
      return;
    }
    int m = (lx + rx) / 2;
    op_max(l, r, v, 2 * x + 1, lx, m);
    op_max(l, r, v, 2 * x + 2, m, rx);
    values[x] = min(values[2 * x + 1], values[2 * x + 2]);
  }

  void op_min(int l, int r, ll v, int x, int lx, int rx) {
    propagate(x, lx, rx);
    if (lx >= r || rx <= l) return;
    if (lx >= l && rx <= r) {
      apply_mod_op_min(min_operations[x], v);
      apply_mod_op_min(values[x], v);
      return;
    }
    int m = (lx + rx) / 2;
    op_min(l, r, v, 2 * x + 1, lx, m);
    op_min(l, r, v, 2 * x + 2, m, rx);
    values[x] = min(values[2 * x + 1], values[2 * x + 2]);
  }

  void op_max(int l, int r, ll v) { op_max(l, r, v, 0, 0, size); }
  void op_min(int l, int r, ll v) { op_min(l, r, v, 0, 0, size); }

  ll get(int l, int r, int x, int lx, int rx) {
    propagate(x, lx, rx);
    if (lx >= r || rx <= l) return LLONG_MAX - 1;
    if (lx >= l && rx <= r) return values[x];
    int m = (lx + rx) / 2;
    ll s1 = get(l, r, 2 * x + 1, lx, m);
    ll s2 = get(l, r, 2 * x + 2, m, rx);
    return min(s1, s2);
  }

  ll get(int l, int r) { return get(l, r, 0, 0, size); }
};

// int main() {
//   ios::sync_with_stdio(false);
//   cin.tie(nullptr);
//   cout << fixed << setprecision(10);
//   ll n, m;
//   cin >> n >> m;
//   segtree seg;
//   seg.init(n + 2);
//   while (m--) {
//     int t, l, r;
//     ll x;
//     cin >> t >> l >> r >> x;
//     r++;
//     if (t == 1)
//       seg.op_max(l, r, x);
//     else
//       seg.op_min(l, r, x);
//   }
//   for (int i = 0; i < n; i++) cout << seg.get(i, i + 1) << "\n";
// }

void buildWall(int n, int k, int op[], int left[], int right[], int height[],
               int finalHeight[]) {
  segtree seg;
  seg.init(n + 2);
  for (int i = 0; i < k; i++) {
    int t = op[i], l = left[i], r = right[i], x = height[i];
    r++;
    if (t == 1)
      seg.op_max(l, r, x);
    else
      seg.op_min(l, r, x);
  }
  for (int i = 0; i < n; i++) finalHeight[i] = seg.get(i, i + 1);
}

Compilation message

wall.cpp: In member function 'void segtree::propagate(int, int, int)':
wall.cpp:71:9: warning: unused variable 'm' [-Wunused-variable]
   71 |     int m = (lx + rx) / 2;
      |         ^

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 98 ms 8160 KB Output is correct
3 Correct 184 ms 5212 KB Output is correct
4 Correct 591 ms 14820 KB Output is correct
5 Correct 309 ms 14672 KB Output is correct
6 Correct 305 ms 14792 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 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 -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -