/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 324.0 KiB
#2 Accepted 2ms 320.0 KiB
#3 Accepted 178ms 33.207 MiB
#4 Accepted 165ms 32.895 MiB
#5 Accepted 147ms 32.867 MiB
#6 Accepted 142ms 32.801 MiB
#7 Accepted 1ms 324.0 KiB
#8 Accepted 1ms 536.0 KiB
#9 Accepted 111ms 33.219 MiB
#10 Accepted 183ms 32.914 MiB

Code

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

#define print(a) for(auto x:a)cout<<x<<' ';cout<<'\n';
#define debug(x) cout<<#x<<" "<<x<<'\n'
#define int   long long int

const int M = 1e9 + 7;
const int N = 2e5 + 10;

int a[N];

struct node {
    int mn,s,mx,lz, s1;
    node(){
        s1 = s = 0, lz = -1;
    }
};

struct ST {
    vector<node> t;  
    int n;
    ST(int _n){
        n = _n; t.assign(4*n + 10, node());
    }

    node Merge(node a, node b){
        node res;
        res.s1 = a.s1 + b.s1;
        return res;
    }

    void upd(int L,int x,int i,int l,int r) {
        if(l==r) {
            t[i].s = x;
            a[L] = x;
           
           // for(int j = 0; j < 6; j++)cout << a[j] <<' ';cout << '\n';
            if((L > 0 && a[L-1] > a[L]) || (L + 1 < n && a[L] > a[L+1])){
               
               t[i].s1 = 1;
            }else{
               t[i].s1 = 0;
            }
            return;
        }
        int m = (l+r)/2;
        if(L <= m) upd(L, x, 2*i, l, m);
        else upd(L, x, 2*i+1, m+1, r);
        t[i] = Merge(t[2*i], t[2*i+1]);
    }
    void upd(int l, int val){
        upd(l,val,1,0,n-1);
    }

    node qry(int L,int R,int i,int l,int r) {
        if(l >= L && r <= R) return t[i];
        if(l > R || r < L)return node();
        int m=(l+r)/2;

        node left , right;
        if(L <= m)left = qry(L, R, 2*i, l, m);
        if(m < R)right = qry(L, R, 2*i+1, m+1, r);
        return Merge(left, right);
    }
    node qry(int l, int r){
        return qry(l,r,1,0,n-1);
    }  
};

void solve(){
   int n; cin >> n;
   
   for(int i = 0; i < n; i++){
      cin >> a[i];
   }
  

   ST st(n);
   for(int i = 0; i < n; i++){
      st.upd(i, a[i]);
   }

   int q; cin >> q;
   while(q--){
      int x, l, r;
      cin >> x >> l >> r;
      if(x == 1){
         l--;
         st.upd(l, r);
         a[l] = r;
      }else{
         l--, r--;
         if(r - l <= 10){
            bool ok = 1;
            for(int i = l + 1 ; i <= r; i++)ok &= (a[i] >= a[i-1]);
            if(ok)cout << "YES\n";
            else cout << "NO\n";continue;
         }
         if(st.qry(l+3,r-3).s1 > 0){
            cout << "NO\n";continue;
         }
         bool ok = 1;
         for(int i = l+1; i <= l+4; i++){
            ok &= (a[i] >= a[i-1]);
         }
         for(int i = r - 1; i >= r - 4; i--){
            ok &= (a[i] <= a[i+1]);
         }
         if(ok == false)cout << "NO\n";
         else cout << "YES\n";
        
      }
   }
}

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

   int t = 1;   //cin >> t;
   for (int tc = 1; tc <= t; tc++) {
      //cout<<"Case "<<tc<<": ";
      solve();
   }
   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 17:06:05
Judged At
2024-10-03 13:24:09
Judged By
Score
100
Total Time
183ms
Peak Memory
33.219 MiB