/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Wrong Answer 1ms 536.0 KiB
#3 Accepted 156ms 15.059 MiB
#4 Accepted 164ms 14.484 MiB
#5 Accepted 139ms 14.578 MiB
#6 Wrong Answer 139ms 14.43 MiB
#7 Accepted 1ms 532.0 KiB
#8 Wrong Answer 1ms 428.0 KiB
#9 Wrong Answer 155ms 14.922 MiB
#10 Wrong Answer 181ms 14.582 MiB

Code

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

typedef long long ll;
const ll md = 1e9+7;

void fxd(int i, int j, int l, int r, ll ara[], ll seg[], ll dp[], int node) {
    if(i > r || j < l) return;
    if(i == j) {
        seg[node] = ara[i];
        dp[node] = 1;
        return;
    }
    dp[node]=1;
    int mid = (i + j) / 2;
    fxd(i, mid, l, r, ara, seg, dp, node * 2);
    fxd(mid + 1, j, l, r, ara, seg, dp, node * 2 + 1);
    if(!dp[node * 2] || !dp[node * 2 + 1] || seg[node * 2] > seg[node * 2 + 1]) dp[node] = 0;
    seg[node] = max(seg[node * 2], seg[node * 2 + 1]);
}

int fnd(int i, int j, int l, int r, ll seg[], ll dp[], ll node) {
    if(i > r || j < l) return 1;
    if(i >= l && j <= r) return dp[node];
    int mid = (i + j) / 2;
    int x = fnd(i, mid, l, r, seg, dp, node * 2);
    int y = fnd(mid + 1, j, l, r, seg, dp, node * 2 + 1);
    if(!x || !y) return 0;
    else return 1;
}

void solve() {
    int n;
    scanf("%d", &n);
    ll ara[n + 1];
    for(int i = 1; i <= n; i++) scanf("%lld", &ara[i]);
    ll seg[4 * n + 10];
    ll dp[4 * n + 10];
    for(int i = 1; i < 4 * n + 10; i++) dp[i] = 1;
    fxd(1, n, 1, n, ara, seg, dp, 1);
    int q;
    scanf("%d", &q);
    while(q--) {
        int a;
        scanf("%d", &a);
        if(a == 1) {
            int i;
            ll x;
            scanf("%d %lld", &i, &x);
            ara[i] = x;
            fxd(1, n, i, i, ara, seg, dp, 1);
        } else {
            int l, r;
            scanf("%d %d", &l, &r);
            int ans = fnd(1, n, l, r, seg, dp, 1);
            if(ans) printf("YES\n");
            else printf("NO\n");
        }
    }
}

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

    int T;
    T = 1; 
    while (T--) {
        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 16:54:57
Judged At
2024-10-03 13:24:57
Judged By
Score
50
Total Time
181ms
Peak Memory
15.059 MiB