/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 328.0 KiB
#2 Accepted 1ms 324.0 KiB
#3 Accepted 78ms 5.711 MiB
#4 Accepted 80ms 6.875 MiB
#5 Accepted 68ms 6.906 MiB
#6 Accepted 68ms 5.41 MiB
#7 Accepted 1ms 324.0 KiB
#8 Accepted 1ms 320.0 KiB
#9 Accepted 84ms 7.277 MiB
#10 Accepted 96ms 6.949 MiB

Code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pe(c) for (auto &e : c) cout << e << ' '; cout << '\n'
#define ps(b) cout << (b ? "YES" : "NO") << '\n'
#define pc cout << "Case " << tc << ": "
#ifdef LOCAL
#include "def.h"
#else
#define ck(...)
#endif
const ll M = 1e9 + 7, N = 2e5 + 5;

long long tre[N << 2], ar[N], n;
void make() {
	for (int i = 0; i < n; ++i)	tre[n + i] = ar[i];
	for (int i = n - 1; i > 0; --i)	tre[i] = tre[i << 1] + tre[i << 1 | 1];
}
void up(auto in, auto val) {
	in += n; tre[in] = val;
	for (int i = in; i > 1; i >>= 1) tre[i >> 1] = tre[i] + tre[i ^ 1];
}
long long sum(auto l, auto r) {
	long long res = 0;
	for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
		if (l & 1) res += tre[l++]; if (r & 1) res += tre[--r];
	}
	return res;
}

void test(int tc) {
	ll a = 0, b = 0, c = 0, d = 0, i = 0, j = 0, k = 0, q = 0;
	cin >> n;
	ll ar1[n+5]; ar1[0]=0; ar[n]=M;
    for(i=1;i<=n;++i) {
        cin >> ar1[i];
        if(ar1[i]<ar1[i-1]) ar[i-1]=1;
    }
    make();
    cin>>q;
    while(q--){
        cin >> a>>b>>c;
        if(a==1){
            ar1[b] = c;
            if(ar1[b]<ar1[b-1]){
                up(b-1, 1);
            }
            else if(ar1[b]>=ar1[b-1]) up(b-1, 0);
            if(ar1[b]>ar1[b+1]){
                up(b, 1);
            }
            if(ar1[b]<=ar1[b+1]){
                up(b, 0);
            }
        }
        else{
            ps(!sum(b, c));
        }
    }
//  	cout << '\n';
}

signed main() {
	cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit|cin.badbit);
	int tc = 0, t = 1;
// 	cin >> t;
	while (tc < t) test(++tc);
	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:38:42
Judged At
2024-10-03 13:21:14
Judged By
Score
100
Total Time
96ms
Peak Memory
7.277 MiB