/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 17ms 18.859 MiB
#2 Wrong Answer 16ms 18.816 MiB
#3 Accepted 109ms 21.27 MiB
#4 Accepted 118ms 20.609 MiB
#5 Accepted 96ms 20.57 MiB
#6 Wrong Answer 95ms 20.691 MiB
#7 Accepted 16ms 18.816 MiB
#8 Wrong Answer 16ms 18.742 MiB
#9 Wrong Answer 124ms 20.918 MiB
#10 Wrong Answer 144ms 20.711 MiB

Code

/**
 *  written by Binoy Barman .
**/

#include<bits/stdc++.h>
using namespace std;
#define nl '\n'
#define all(v) v.begin(), v.end()
#define Too_Many_Jobs int tts, tc = 1; cin >> tts; hell: while(tts--)
#define Dark_Lord_Binoy ios_base::sync_with_stdio(false); cin.tie(NULL);

#ifdef LOCAL
#include "unravel.hpp"
#else
#define dbg(...) 42
#endif
#define int long long

const int N = 2e5 + 9;

struct node {
    int l;
    int r;
    bool ok;
};

int a[N];
struct SegmentTree {
    node t[4 * N];
    static const int inf = 1e9;
    SegmentTree() {
        memset(t, 0, sizeof t);
    }
    void build(int n, int b, int e) {
        if (b == e) {
            t[n].l = a[b];
            t[n].r = a[b];
            t[n].ok = true;
            return;
        }
        int mid = (b + e) >> 1, l = n << 1, r = l | 1;
        build(l, b, mid);
        build(r, mid + 1, e);
        t[n].l = t[l].l;
        t[n].r = t[r].r;
        if(t[l].ok && t[r].ok && t[l].r <= t[r].l) t[n].ok = true;
        else t[n].ok = false;
    }
    void upd(int n, int b, int e, int i, int x) {
        if (b > i || e < i) return;
        if (b == e && b == i) {
            t[n].l = x; 
            t[n].r = x; 
            t[n].ok = true; 
            return;
        }
        int mid = (b + e) >> 1, l = n << 1, r = l | 1;
        upd(l, b, mid, i, x);
        upd(r, mid + 1, e, i, x);
        t[n].l = t[l].l;
        t[n].r = t[r].r;
        if(t[l].ok && t[r].ok && t[l].r <= t[r].l) t[n].ok = true;
        else t[n].ok = false;
    }
    bool query(int n, int b, int e, int i, int j) {
        if (b > j || e < i) return true; // return approriate value
        if (b >= i && e <= j) return t[n].ok;
        int mid = (b + e) >> 1, l = n << 1, r = l | 1;
        bool L = query(l, b, mid, i, j);
        bool R = query(r, mid + 1, e, i, j);
        return (L & R);
    }
}t;

int32_t main() {
Dark_Lord_Binoy
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int n, q;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    t.build(1, 1, n);
    cin >> q;
    while(q--) {
        int c, l, r;
        cin >> c >> l >> r;
        if(c == 1) {
            t.upd(1, 1, n, l, r);
        }
        else {
            cout << (t.query(1, 1, n, l, r) ? "YES" : "NO") << nl;
        }
    }

    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:18:06
Judged At
2024-10-03 13:27:41
Judged By
Score
50
Total Time
144ms
Peak Memory
21.27 MiB