/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 13ms 14.25 MiB
#2 Accepted 12ms 14.812 MiB
#3 Accepted 237ms 15.684 MiB
#4 Accepted 206ms 15.355 MiB
#5 Accepted 182ms 15.352 MiB
#6 Accepted 185ms 15.52 MiB
#7 Accepted 11ms 14.703 MiB
#8 Accepted 12ms 14.305 MiB
#9 Accepted 224ms 15.672 MiB
#10 Wrong Answer 227ms 15.309 MiB

Code

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

const int N = 3e5 + 9;
const int inf = 1e9+7;

int a[N];

struct ST
{
    struct Node
    {
        bool isSorted;
        int minVal, maxVal;
    } t[4 * N];

    ST()
    {
        memset(t, 0, sizeof t);
    }

    Node merge(Node left, Node right)
    {
        Node parent;
        parent.isSorted = left.isSorted && right.isSorted && (left.maxVal <= right.minVal);
        parent.minVal = min(left.minVal, right.minVal);
        parent.maxVal = max(left.maxVal, right.maxVal);
        return parent;
    }

    void build(int n, int b, int e)
    {
        if (b == e)
        {
            t[n].isSorted = true;
            t[n].minVal = a[b];
            t[n].maxVal = a[b];
            return;
        }
        int mid = (b + e) >> 1;
        build(n << 1, b, mid);
        build(n << 1 | 1, mid + 1, e);
        t[n] = merge(t[n << 1], t[n << 1 | 1]);
    }

    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].isSorted = true;
            t[n].minVal = x;
            t[n].maxVal = x;
            return;
        }
        int mid = (b + e) >> 1;
        upd(n << 1, b, mid, i, x);
        upd(n << 1 | 1, mid + 1, e, i, x);
        t[n] = merge(t[n << 1], t[n << 1 | 1]);
    }

    Node query(int n, int b, int e, int i, int j)
    {
        if (b > j || e < i)
            return {true, inf, -inf}; // Neutral value for merging
        if (b >= i && e <= j)
            return t[n];
        int mid = (b + e) >> 1;
        Node leftQuery = query(n << 1, b, mid, i, j);
        Node rightQuery = query(n << 1 | 1, mid + 1, e, i, j);
        return merge(leftQuery, rightQuery);
    }

    void update(int idx, int value)
    {
        upd(1, 1, N - 1, idx, value);
    }

    bool isSorted(int L, int R)
    {
        return query(1, 1, N - 1, L, R).isSorted;
    }
} t;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    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 type;
        cin >> type;

        if (type == 1)
        {
            int i, x;
            cin >> i >> x;
            t.update(i, x);
        }
        else if (type == 2)
        {
            int l, r;
            cin >> l >> r;
            auto anss = t.query(1, 1, N, l, r);
            // cout << anss.isSorted << '\n';
            if (anss.isSorted)
                cout << "YES\n";
            else
                cout << "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:47:35
Judged At
2024-10-03 13:25:58
Judged By
Score
90
Total Time
237ms
Peak Memory
15.684 MiB