/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Wrong Answer 1ms 532.0 KiB
#3 Accepted 107ms 8.035 MiB
#4 Accepted 112ms 7.457 MiB
#5 Accepted 93ms 7.613 MiB
#6 Wrong Answer 93ms 7.477 MiB

Code

// @sagorahmedmunna

#include <bits/stdc++.h>
using namespace std;

struct SegTree {
  struct node {
    int l, r, sum;
    node() {
      l = r = sum = 0;
    }
  };
  int size = 1;
  vector<node> st;
  SegTree(int n) {
    size = n;
    int tree_size = 1;
    while (tree_size < n) tree_size *= 2;
    st.resize(tree_size * 2);
  }
  node make_node(int val) {
    node res;
    res.l = res.r = val;
    res.sum = 0;
    return res;
  }
  node Merge(node& L, node& R) {
    node res;
    res.sum = L.sum + R.sum;
    res.l = L.l;
    res.r = R.r;
    if (L.r > R.l) {
      res.sum++;
    }
    return res;
  }
  void build(int u, int s, int e, vector<int>& a) {
    if (s == e) {
      st[u] = make_node(a[s]);
      return;
    }
    int v = 2 * u, w = 2 * u + 1, m = (s + e) / 2;
    build(v, s, m, a);
    build(w, m + 1, e, a);
    st[u] = Merge(st[v], st[w]);
  }
  void build(vector<int>& a) {
    build(1, 1, size, a);
  }
  void update(int u, int s, int e, int k, int val) {
    if (s == e) {
      st[u] = make_node(val);
      return;
    }
    int v = 2 * u, w = 2 * u + 1, m = (s + e) / 2;
    if (k <= m) update(v, s, m, k, val);
    else update(w, m + 1, e, k, val);
    st[u] = Merge(st[v], st[w]);
  }
  void update(int k, int val) {
    update(1, 1, size, k, val);
  }
  int query(int u, int s, int e, int l, int r) {
    if (e < l || r < s) {
      return 0;
    }
    if (l <= s && e <= r) return st[u].sum;
    int v = 2 * u, w = 2 * u + 1, m = (s + e) / 2;
    int lsum = query(v, s, m, l, r);
    int rsum = query(w, m + 1, e, l, r);
    return lsum + rsum;
  }
  int query(int l, int r) {
    return query(1, 1, size, l, r);
  }
};

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  
  int n;
  cin >> n;
  vector<int> a(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  SegTree sg(n);
  sg.build(a);
  int q;
  cin >> q;
  while (q--) {
    int type;
    cin >> type;
    if (type == 1) {
      int i, x;
      cin >> i >> x;
      sg.update(i, x);
    } else {
      int l, r;
      cin >> l >> r;
      cout << (sg.query(l, r) == 0 ? "YES" : "NO") << '\n';
    }
  }
  return 0;
}

Information

Submit By
Type
Submission
Problem
P1085 Sorted or !Sorted
Contest
Bangladesh 2.0
Language
C++20 (G++ 13.2.0)
Submit At
2024-08-16 16:30:10
Judged At
2024-11-11 03:14:38
Judged By
Score
40
Total Time
112ms
Peak Memory
8.035 MiB