/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 2ms 320.0 KiB
#3 Accepted 582ms 4.672 MiB
#4 Accepted 406ms 4.227 MiB
#5 Accepted 376ms 4.312 MiB
#6 Wrong Answer 373ms 4.25 MiB
#7 Accepted 1ms 324.0 KiB
#8 Wrong Answer 1ms 320.0 KiB
#9 Wrong Answer 570ms 4.645 MiB
#10 Wrong Answer 489ms 4.312 MiB

Code

// Segment Tree 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
 
const int mx = 2e5+20;

int tree[mx * 4] , arr[mx], a[mx];

void build(int node, int b, int e){
	if (b == e){
		tree[node] = arr[b];
		return;
	}
	int left = node * 2;
	int right = node * 2 + 1;
	int mid = (b + e) >> 1;

	build(left, b, mid);
	build(right, mid + 1, e);
	//int 
	tree[node] = min(tree[left], tree[right]);
}

int query(int node, int b, int e, int i, int j){
	if (b >= i && e <= j){
		return tree[node];
	}
	if (e < i || b > j){
		return 1;
	}
	int left = node << 1;
	int right = (node << 1)+1;
	int mid = (b + e) >> 1;
	
	int leftMax = query(left, b, mid, i , j);
	int rightMax = query(right, mid + 1, e, i, j);
	
	return min(leftMax, rightMax);
}

void update(int node, int b, int e, int index, int value){
	if (b >= index && e <= index){
		tree[node] = value;
		return;
	}
	if(b > index || e < index){
		return;
	}
	int left = node * 2;
	int right = node * 2 + 1;
	int mid = (b + e) >> 1;

	update(left, b, mid, index, value);
	update(right, mid + 1, e , index , value);

	tree[node] = min(tree[left], tree[right]);
}

int main(){
  int n, q, m;
  cin>>n;
  for (int i = 1; i <= n; i++) arr[i] = 1;
  for(int i = 1; i <= n; i++){
   	cin>>a[i];
   	if (a[i] < a[i - 1]) arr[i] = 0;
  }
  build(1, 1, n);
  cin >> q;
  while (q--){
    cin >> m;
    if (m == 1){
      int idx, x;
      cin >> idx >> x;
      a[idx] = x;
      if (a[idx] < a[idx - 1]) x = 0;
      else x = 1;
      update(1, 1, n, idx, x);
    } else {
      int L, R; 
      cin >> L >> R;
      if (L == R || L+1==R){
        cout << "YES" << endl;
        continue;
      }
      int ok = query(1, 1, n, L+1, R);
      if (ok == 1) cout << "YES" << endl;
      else cout << "NO" << endl;
    }
  }
  /*cout<< query(1, 1, n, 2, 5)<<endl;
  update(1, 1, n, 4, 2);
  cout<<query(1,1,n,3,3);*/
}

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 17:10:52
Judged At
2024-10-03 13:23:43
Judged By
Score
60
Total Time
582ms
Peak Memory
4.672 MiB