/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 320.0 KiB
#2 Accepted 1ms 320.0 KiB
#3 Accepted 92ms 12.02 MiB
#4 Accepted 91ms 11.531 MiB
#5 Accepted 77ms 11.508 MiB
#6 Accepted 77ms 11.449 MiB
#7 Accepted 1ms 328.0 KiB
#8 Accepted 1ms 528.0 KiB
#9 Accepted 93ms 11.816 MiB
#10 Accepted 105ms 11.406 MiB

Code

// #pragma GCC optimize("O3,unroll-loops,Ofast")
// #pragma GCC target("avx2")
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
#define int long long
#define endl '\n'

using namespace std;
using pii = pair<int, int>;
using tup = tuple<int, int, int>;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// template <class T> using ordered_set = tree<T, null_type,
//                          less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int inf = (1e15)+5;
const int mod = 1000000007;
const double eps = 1e-6;
const int N = 200005;

void preprocess() {}

int a[N];

struct Node {
    int mn, mx;
    int sorted;
 
    Node() {
        mn = inf; mx = -inf;
        sorted = 1;
    }
    Node(int val) {
        mn = mx = val;
        sorted = 1;
    }
};

struct ST {
  int n;
  Node *t;
  ST(int _n) { n = _n; t = new Node[2 * n]; }
  inline Node combine(Node l, Node r) {
    Node res;
    res.mn = min(l.mn, r.mn);
    res.mx = max(l.mx, r.mx);
    res.sorted = (l.sorted && r.sorted && l.mx <= r.mn);
    return res;
  }
  void build() {
    for(int i = 0; i < n; i++) t[i + n] = Node(a[i+1]);
    for(int i = n - 1; i > 0; --i) t[i] = combine(t[i << 1], t[i << 1 | 1]);
  }
  void upd(int p, int v) {
    p--;
    for (t[p += n] = Node(v); p >>= 1; ) t[p] = combine(t[p << 1], t[p << 1 | 1]);
  }

  Node query(int l, int r) {
    --l;
    bool f1 = 1, f2 = 1;
    Node resl, resr;
    for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if(l & 1) resl = f1 ? t[l++] : combine(resl, t[l++]), f1 = 0;
      if(r & 1) resr = f2 ? t[--r] : combine(t[--r], resr), f2 = 0;
    }
    if(f2) return resl;
    if(f1) return resr;
    return combine(resl, resr);
  }
};
// Works well with PRAGMAS
// Try not to make l > r queries


void solve(int tc) {
	int n, q;
	cin >> n;

	for(int i=1; i<=n; i++) cin >> a[i];

	ST st(n);
	st.build();

	cin >> q;
	while(q--) {
		int t, l, r, p, x;
		cin >> t;
		if(t == 2) {
			cin >> l >> r;
			Node res = st.query(l, r);
			cout << (res.sorted ? "YES" : "NO") << endl;
		} else {
			cin >> p >> x;
			st.upd(p, x);
		}
	}
}
    
int32_t main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cout.precision(10);

    preprocess();

    int T = 1;
    // cin >> T;

    for (int i = 1; i <= T; i++) {
        solve(i);
    }

    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:22:07
Judged At
2024-11-11 03:15:00
Judged By
Score
100
Total Time
105ms
Peak Memory
12.02 MiB