/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 324.0 KiB
#2 Accepted 2ms 324.0 KiB
#3 Accepted 577ms 10.461 MiB
#4 Accepted 441ms 9.984 MiB
#5 Accepted 392ms 9.957 MiB
#6 Accepted 392ms 9.988 MiB
#7 Accepted 1ms 524.0 KiB
#8 Accepted 1ms 532.0 KiB
#9 Accepted 644ms 10.273 MiB
#10 Accepted 515ms 9.996 MiB

Code

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

class SGTree
{
    vector<int> seg;

public:
    SGTree(int n)
    {
        seg.resize(4 * n);
    }
    void build(int ind, int low, int high, int b[])
    {
        if (low == high)
        {
            seg[ind] = b[low]; // CHANGE
            return;
        }
        int mid = (low + high) >> 1;
        build(2 * ind + 1, low, mid, b);
        build(2 * ind + 2, mid + 1, high, b);
        seg[ind] = (seg[2 * ind + 1] + seg[2 * ind + 2]); // CHANGE
    }
    void update(int ind, int low, int high, int i, int val)
    {
        if (low == high)
        {
            seg[ind] = val; // CHANGE
            return;
        }
        int mid = (low + high) >> 1;
        if (i <= mid)
            update(2 * ind + 1, low, mid, i, val);
        else
            update(2 * ind + 2, mid + 1, high, i, val);
        seg[ind] = (seg[2 * ind + 1] + seg[2 * ind + 2]); // CHANGE
    }

    int query(int ind, int low, int high, int l, int r)
    {

        // no overlap
        // l r low high or low high l r
        if (high < l or r < low)
        {
            return 0; // CHANGE
        }

        // complete overlap
        // [l low high r]
        if (low >= l && high <= r)
            return seg[ind]; // CHANGE

        int mid = (low + high) >> 1;
        int left = query(2 * ind + 1, low, mid, l, r);
        int right = query(2 * ind + 2, mid + 1, high, l, r);
        return left + right; // CHANGE
    }
};
main()
{
    int n, i, q;
    cin >> n ;
    int arr[n + 5];
    int b[n + 5];
    arr[0] = 0;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
    arr[n + 1] = 2e9;
    for (int i = 1; i <= n; i++)
        b[i] = (arr[i - 1] <= arr[i]) ? 1 : 0;
    SGTree st(n);
    st.build(1, 1, n, b);
   //  int q;
    cin >> q;
    while (q--)
    {
        int type;
        cin >> type;
        if (type == 2)
        {
            int l, r;
            cin >> l >> r;
            int x = st.query(1, 1, n, 1, r);
            int y = st.query(1, 1, n, 1, l);
            if ((x-y) == (r - l))
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
        }
        else
        {
            int l, r, val;
            cin >> i >> val;
            if (arr[i - 1] <= arr[i])
            {
                st.update(1, 1, n, i, -1);
            }
            else
            {
                st.update(1, 1, n, i, +1);
            }
            if ((i + 1) != n)
            {
                if (arr[i] <= arr[i+1])
                {
                    st.update(1, 1, n, i+1, -1);
                }
                else
                {
                    st.update(1, 1, n, i+1, +1);
                }
            }
            arr[i] = val;
             if (arr[i - 1] <= arr[i])
            {
                st.update(1, 1, n, i, +1);
            }
            else
            {
                st.update(1, 1, n, i, -1);
            }
            if ((i + 1) != n)
            {
                if (arr[i] <= arr[i+1])
                {
                    st.update(1, 1, n, i+1, +1);
                }
                else
                {
                    st.update(1, 1, n, i+1, -1);
                }
            }
        }
    }
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1085 Sorted or !Sorted
Contest
Bangladesh 2.0
Language
C++17 (G++ 13.2.0)
Submit At
2024-08-16 16:26:37
Judged At
2024-10-03 13:26:54
Judged By
Score
100
Total Time
644ms
Peak Memory
10.461 MiB