oj.uz

Submission #915720

# Submission time Handle Problem Language Result Execution time Memory
915720 2024-01-24T15:45:48 Z Bubu_Orange Simple (info1cup19_simple) C++14
60 / 100
 273 ms 33624 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(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;
        if(a<=mid){
            query(2*node, left, mid, a, b);
        }
        if(b>mid){
            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 4 ms 4700 KB Output is correct
2 Correct 5 ms 4700 KB Output is correct
3 Correct 6 ms 7028 KB Output is correct
4 Correct 5 ms 7004 KB Output is correct
5 Correct 6 ms 7004 KB Output is correct
6 Correct 5 ms 6932 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 15536 KB Output is correct
2 Correct 187 ms 28812 KB Output is correct
3 Correct 180 ms 28716 KB Output is correct
4 Correct 172 ms 28716 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4700 KB Output is correct
2 Correct 5 ms 4700 KB Output is correct
3 Correct 6 ms 7028 KB Output is correct
4 Correct 5 ms 7004 KB Output is correct
5 Correct 6 ms 7004 KB Output is correct
6 Correct 5 ms 6932 KB Output is correct
7 Correct 92 ms 15536 KB Output is correct
8 Correct 187 ms 28812 KB Output is correct
9 Correct 180 ms 28716 KB Output is correct
10 Correct 172 ms 28716 KB Output is correct
11 Correct 112 ms 20340 KB Output is correct
12 Incorrect 273 ms 33624 KB Output isn't correct
13 Halted 0 ms 0 KB -