oj.uz

Submission #915722

# Submission time Handle Problem Language Result Execution time Memory
915722 2024-01-24T15:47:44 Z Bubu_Orange Simple (info1cup19_simple) C++14
60 / 100
 288 ms 27984 KB 
#include<bits/stdc++.h>

using namespace std;

// ifstream in("simple.in");
// ofstream out("simple.out");

struct nod{
    long long mnp, mni, mxp, mxi;
};

long long n, q, mx, mn, T, A, B, x;
long long v[200005];
nod tree[800005];
long long lazy[800005];

void build(long long node, long long left, long long right){
    //lazy[node]=-1;
    if(left==right){
        if(v[left]%2==0){
            tree[node].mnp=v[left];
            tree[node].mni=LONG_LONG_MAX;
            tree[node].mxi=LONG_LONG_MIN;
            tree[node].mxp=v[left];
        }else{
            tree[node].mni=v[left];
            tree[node].mnp=LONG_LONG_MAX;
            tree[node].mxp=LONG_LONG_MIN;
            tree[node].mxi=v[left];
        }
        // ccout<<left<<" "<<right<<" | "<<tree[node].mnp<<" "<<tree[node].mni<<" "<<tree[node].mxp<<" "<<tree[node].mxi<<'\n';
    }else{
        long long mid=(left+right)/2;

        build(node*2, left, mid);
        build(node*2+1, mid+1, right);

        tree[node].mxp=max(tree[node*2].mxp, tree[node*2+1].mxp);
        tree[node].mxi=max(tree[node*2].mxi, tree[node*2+1].mxi);
        tree[node].mnp=min(tree[node*2].mnp, tree[node*2+1].mnp);
        tree[node].mni=min(tree[node*2].mni, tree[node*2+1].mni);
    }
}

void update_lazy(long long node, long long st, long long dr){
    if(lazy[node]==0){
        return;
    }
    if(tree[node].mxp!=LONG_LONG_MIN){
        tree[node].mxp+=lazy[node];
    }
    if(tree[node].mnp!=LONG_LONG_MAX){
        tree[node].mnp+=lazy[node];
    }
    if(tree[node].mxi!=LONG_LONG_MIN){
        tree[node].mxi+=lazy[node];
    }
    if(tree[node].mni!=LONG_LONG_MAX){
        tree[node].mni+=lazy[node];
    }
    if(lazy[node]%2==1){
        swap(tree[node].mxp, tree[node].mxi);
        swap(tree[node].mnp, tree[node].mni);
    }
    if(left!=right){
        //cout<<node<<" ";
        lazy[2*node]+=lazy[node];
        lazy[2*node+1]+=lazy[node];
    }
    lazy[node]=0;
}

void update(long long node, long long left, long long right, long long a, long long b, long long val){
    update_lazy(node, left, right);
    if(right<a||b<left){
        return;
    }
    if(a<=left&&right<=b){
        lazy[node]+=val;
        update_lazy(node, left, right);
        return;
    }
    long long mid=(left+right)/2;
    update(2*node, left, mid, a, b, val);
    update(2*node+1, mid+1, right, a, b, val);
    // update_lazy(2*node, left, mid);
    // update_lazy(2*node+1, mid+1, right);
    tree[node].mnp=min(tree[2*node].mnp, tree[2*node+1].mnp);
    tree[node].mni=min(tree[2*node].mni, tree[2*node+1].mni);
    tree[node].mxp=max(tree[2*node].mxp, tree[2*node+1].mxp);
    tree[node].mxi=max(tree[2*node].mxi, tree[2*node+1].mxi);
    //ccout<<a<<" "<<b<<" | "<<left<<" "<<right<<" | "<<tree[node].mnp<<" "<<tree[node].mni<<" "<<tree[node].mxp<<" "<<tree[node].mxi<<'\n';
}

void query(long long node, long long left, long long right, long long a, long long b){
    update_lazy(node, left, right);
    if(right<a||b<left){
        return;
    }
    if(a<=left&&right<=b){
        mx=max(mx, tree[node].mxi);
        mn=min(mn, tree[node].mnp);
        //ccout<<a<<" "<<b<<" | "<<left<<" "<<right<<" | "<<tree[node].mnp<<" "<<tree[node].mni<<" "<<tree[node].mxp<<" "<<tree[node].mxi<<'\n';
    }else{
        long long mid=(left+right)/2;
        query(2*node, left, mid, a, b);
        query(2*node+1, mid+1, right, a, b);
    }
}

int main(){
    // ifstream cin("simple.in");
    // ofstream cout("simple.out");
    //memset(lazy, -1, sizeof(lazy));
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n;
    for(long long i=1; i<=n; i++){
        cin>>v[i];
    }
    cin>>q;
    build(1, 1, n);
    for(long long i=1; i<=q; i++){
        cin>>T>>A>>B;
        if(T==0){
            cin>>x;
            update(1, 1, n, A, B, x);
        }else{
            mn=LONG_LONG_MAX;
            mx=LONG_LONG_MIN;
            query(1, 1, n, A, B);
            if(mn==LONG_LONG_MAX){
                cout<<-1<<" ";
            }else{
                cout<<mn<<" ";
            }
            if(mx==LONG_LONG_MIN){
                cout<<-1<<'\n';
            }else{
                cout<<mx<<'\n';
            }
        }
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4696 KB Output is correct
2 Correct 5 ms 4700 KB Output is correct
3 Correct 6 ms 6932 KB Output is correct
4 Correct 5 ms 6748 KB Output is correct
5 Correct 5 ms 6856 KB Output is correct
6 Correct 6 ms 6748 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 13176 KB Output is correct
2 Correct 191 ms 23888 KB Output is correct
3 Correct 174 ms 23892 KB Output is correct
4 Correct 169 ms 23932 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4696 KB Output is correct
2 Correct 5 ms 4700 KB Output is correct
3 Correct 6 ms 6932 KB Output is correct
4 Correct 5 ms 6748 KB Output is correct
5 Correct 5 ms 6856 KB Output is correct
6 Correct 6 ms 6748 KB Output is correct
7 Correct 79 ms 13176 KB Output is correct
8 Correct 191 ms 23888 KB Output is correct
9 Correct 174 ms 23892 KB Output is correct
10 Correct 169 ms 23932 KB Output is correct
11 Correct 120 ms 17632 KB Output is correct
12 Incorrect 288 ms 27984 KB Output isn't correct
13 Halted 0 ms 0 KB -