/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 336.0 KiB
#2 Wrong Answer 2ms 540.0 KiB
#3 Accepted 288ms 21.18 MiB
#4 Accepted 335ms 20.656 MiB
#5 Accepted 266ms 20.711 MiB
#6 Wrong Answer 254ms 20.711 MiB
#7 Accepted 2ms 332.0 KiB
#8 Wrong Answer 2ms 564.0 KiB
#9 Wrong Answer 278ms 21.07 MiB
#10 Wrong Answer 352ms 20.703 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 seg2[], ll dp[], int node) {
    if(i > r || j < l) return;
    if(i == j) {
        seg[node] = ara[i];
        seg2[node]=ara[i];
        dp[node] = 1;
        return;
    }
    dp[node]=1;
    int mid = (i + j) / 2;
    fxd(i, mid, l, r, ara, seg,seg2, dp, node * 2);
    fxd(mid + 1, j, l, r, ara, seg,seg2, dp, node * 2 + 1);
    if(!dp[node * 2] || !dp[node * 2 + 1] || seg[node * 2] > seg2[node * 2 + 1]) dp[node] = 0;
    seg[node]=max(seg[node*2+1],seg[node*2]);
    seg2[node]=min(seg2[node*2],seg2[node*2+1]);
}

int fnd(int i, int j, int l, int r, 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,  dp, node * 2);
    int y = fnd(mid + 1, j, l, r,  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 seg1[4 * n + 10];
     ll seg2[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, seg1,seg2, 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, seg1,seg2, dp, 1);
        } else {
            int l, r;
            scanf("%d %d", &l, &r);
            int ans = fnd(1, n, l, r,  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 17:05:03
Judged At
2024-10-03 13:24:11
Judged By
Score
50
Total Time
352ms
Peak Memory
21.18 MiB