/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 532.0 KiB
#2 Accepted 1ms 324.0 KiB
#3 Accepted 174ms 11.09 MiB
#4 Accepted 151ms 10.598 MiB
#5 Accepted 134ms 10.762 MiB
#6 Accepted 136ms 10.574 MiB
#7 Accepted 1ms 428.0 KiB
#8 Accepted 1ms 320.0 KiB
#9 Accepted 150ms 10.871 MiB
#10 Accepted 165ms 10.77 MiB

Code

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

#define all(v) v.begin(), v.end()

using LL = long long;

struct node {
  int left, right;
  bool good;
  node (int _left = -1, int _right = -1, bool _good = true) : left(_left), right(_right), good(_good) {}
};

template <typename VT>
class segtree {
  using DT = typename VT :: DT;
  private:
    int L, R;
    vector <DT> tr;
  public:
    segtree (int n): L (0), R (n - 1), tr (n << 2) {}
    segtree (int l, int r): L (l), R (r), tr ((r - l + 1) << 2) {}
    void build (int curLeft, int curRight, vector <int> &v, int pos = 1 ) {
      if (curLeft == curRight) {
        tr[pos] = node (v[curLeft], v[curLeft], true);
        return;
      }
      int mid = (curLeft + curRight) >> 1, lft = pos << 1, ryt = pos << 1 | 1;
      build (curLeft, mid, v, lft);
      build (mid + 1, curRight, v, ryt);
      tr[pos] = VT :: merge (tr[lft], tr[ryt]);
    }
    void update (int curLeft, int curRight, int updated_val, int idx, int pos = 1) {
      if (curLeft == curRight) {
        tr[pos] = node (updated_val, updated_val, true);
        return;
      }
      int mid = (curLeft + curRight) >> 1, lft = pos << 1, ryt = pos << 1 | 1;
      if (idx <= mid) update (curLeft, mid, updated_val, idx, lft);
      else update (mid + 1, curRight, updated_val, idx, ryt);
      tr[pos] = VT :: merge (tr[lft], tr[ryt]);
    }
    DT query (int curLeft, int curRight, int l, int r, int pos = 1) {
      if (r < curLeft or l > curRight or l > r) return VT :: I;
      if (curLeft >= l and curRight <= r) return tr[pos];
      
      int mid = (curLeft + curRight) >> 1, lft = pos << 1, ryt = pos << 1 | 1;
      DT ansl = query (curLeft, mid, l, r, lft);
      DT ansr = query (mid + 1, curRight, l, r, ryt);
      return VT :: merge (ansl, ansr);
    }
    void build (vector <int> &v) { build(L, R, v); }
    void update (int idx, int U) { update (L, R, U, idx); }
    DT query (int ql, int qr) { return query(L, R, ql, qr); }
};

/**************************************************************/
/*                 DON'T CHANGE ABOVE THIS                    */

struct sorted {
  using DT = node; 
  static const DT I;
  static DT merge (const DT &a, const DT &b) {
    if (a.left == -1) return b;
    else if (b.left == -1) return a;
    else return node (a.left, b.right, ((a.right <= b.left) & a.good & b.good));
  }
};

const node sorted :: I = node();

/* 
Initialize: segtree <add_sum> Tree (n); == 0-based indexing
            segtree <add_sum> Tree (1, n); == 1-based indexing
Operations: Tree.update (val, idx) == update idx index with val
            Tree.query (l, r); == query in range [l, r]
*/

int main() {
  cin.tie (nullptr) -> ios_base :: sync_with_stdio (false);

  int n;
  cin >> n;
  vector <int> v (n);
  for (auto &i : v) cin >> i;
  segtree <sorted> Tree (n);
  Tree.build (v);
  int q;
  cin >> q;
  while (q--) {
    int type;
    cin >> type;
    if (type == 1) {
      int idx, val;
      cin >> idx >> val;
      Tree.update (--idx, val);
    } else {
      int l, r;
      cin >> l >> r;
      cout << ((Tree.query (--l, --r).good) ? "YES" : "NO") << '\n';
    }
  }

  return 0;
}

Information

Submit By
Type
Submission
Problem
P1085 Sorted or !Sorted
Language
C++20 (G++ 13.2.0)
Submit At
2024-08-16 19:47:25
Judged At
2024-10-03 13:20:04
Judged By
Score
100
Total Time
174ms
Peak Memory
11.09 MiB