제출 #1130129

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1130129		matthew	Simple (info1cup19_simple)	C++20	100 / 100	577 ms	26368 KiB

subway

#include <iostream>
#include <utility>

using ll = long long;
const int MAX_N = 200'000;
const int MAX_LEN = (1 << 18);
const ll INF_LL = 1'000'000'000'000'000'000LL;

struct MinMax {
  ll min, max;

  MinMax operator +(const MinMax &other) {
    return {
      std::min(min, other.min),
      std::max(max, other.max)
    };
  }
};

struct Node {
  ll min[2];
  ll max[2];
  ll lazy;

  Node operator +(const Node &other) {
    return {
      {std::min(min[0], other.min[0]),
       std::min(min[1], other.min[1])},
      {std::max(max[0], other.max[0]),
       std::max(max[1], other.max[1])},
      0
    };
  }
};

struct SegTree {
  int n;
  Node st[2 * MAX_LEN];

  void init(int n, int a[]) {
    this->n = (1 << (32 - __builtin_clz(n - 1)));
    for(int i = 0; i < n; i++) {
      st[i + this->n] = {{INF_LL, INF_LL}, {-1, -1}, 0};
      st[i + this->n].min[a[i] % 2] = st[i + this->n].max[a[i] % 2] = a[i];
    }
    for(int i = n; i < this->n; i++) {
      st[i + this->n] = {{INF_LL, INF_LL}, {-1, -1}, 0};
    }
    for(int i = this->n - 1; i > 0; i--) {
      st[i] = st[2 * i] + st[2 * i + 1];
    }
  }

  void update_node(Node &node, ll val) {
    if(node.min[0] != INF_LL) {
      node.min[0] += val;
    }
    if(node.min[1] != INF_LL) {
      node.min[1] += val;
    }
    if(node.max[0] != -1) {
      node.max[0] += val;
    }
    if(node.max[1] != -1) {
      node.max[1] += val;
    }
    if(val % 2 == 1) {
      std::swap(node.min[0], node.min[1]);
      std::swap(node.max[0], node.max[1]);
    }
  }

  void propagate(int node) {
    if(st[node].lazy > 0) {
      update_node(st[node], st[node].lazy);
      if(node < n) {
        st[2 * node].lazy += st[node].lazy;
        st[2 * node + 1].lazy += st[node].lazy;
      }
      st[node].lazy = 0;
    }
  }

  void pull(int node) {
    propagate(2 * node);
    propagate(2 * node + 1);
    st[node] = st[2 * node] + st[2 * node + 1];
  }

  void _update(int node, int pl, int pr, int l, int r, int val) {
    if(pl > pr || l > r) {
      return;
    }
    if(pl == l && pr == r) {
      st[node].lazy += val;
      return;
    }
    propagate(node);
    int mid = (pl + pr) / 2;
    _update(2 * node, pl, mid, l, std::min(r, mid), val);
    _update(2 * node + 1, mid + 1, pr, std::max(l, mid + 1), r, val);
    pull(node);
  }

  void update(int l, int r, int val) {
    _update(1, 0, n - 1, l, r, val);
  }

  MinMax _query(int node, int pl, int pr, int l, int r) {
    if(pl > pr || l > r) {
      return {INF_LL, -1};
    }
    if(pl == l && pr == r) {
      propagate(node);
      return {st[node].min[0], st[node].max[1]};
    }
    propagate(node);
    int mid = (pl + pr) / 2;
    return _query(2 * node, pl, mid, l, std::min(r, mid)) +
           _query(2 * node + 1, mid + 1, pr, std::max(l, mid + 1), r);
  }

  MinMax query(int l, int r) {
    return _query(1, 0, n - 1, l, r);
  }
};

int a[MAX_N];
SegTree st;

int main() {
  int n;
  std::cin >> n;
  for(int i = 0; i < n; i++) {
    std::cin >> a[i];
  }

  st.init(n, a);
  int q;
  std::cin >> q;
  for(int i = 0; i < q; i++) {
    int type, l, r;
    std::cin >> type >> l >> r;
    if(type == 0) {
      int val;
      std::cin >> val;
      st.update(l - 1, r - 1, val);
    } else {
      MinMax ans = st.query(l - 1, r - 1);
      std::cout << ((ans.min == INF_LL) ? -1 : ans.min) << " " << ans.max << "\n";
    }
  }

  return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40