oj.uz

Submission #915745

# Submission time Handle Problem Language Result Execution time Memory
915745 2024-01-24T16:14:38 Z Bubu_Orange Simple (info1cup19_simple) C++14
60 / 100
 285 ms 33620 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=2000000000000000000;
            tree[node].mxi=0;
            tree[node].mxp=v[left];
        }else{
            tree[node].mni=v[left];
            tree[node].mnp=2000000000000000000;
            tree[node].mxp=0;
            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!=0){
        tree[node].mxp+=lazy[node];
    }
    if(tree[node].mnp!=2000000000000000000){
        tree[node].mnp+=lazy[node];
    }
    if(tree[node].mxi!=0){
        tree[node].mxi+=lazy[node];
    }
    if(tree[node].mni!=2000000000000000000){
        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=2000000000000000000;
            mx=0;
            query(1, 1, n, A, B);
            if(mn==2000000000000000000){
                cout<<-1<<" ";
            }else{
                cout<<mn<<" ";
            }
            if(mx==0){
                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 4824 KB Output is correct
2 Correct 6 ms 4696 KB Output is correct
3 Correct 6 ms 7040 KB Output is correct
4 Correct 5 ms 7004 KB Output is correct
5 Correct 6 ms 6988 KB Output is correct
6 Correct 5 ms 7004 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 15444 KB Output is correct
2 Correct 181 ms 28804 KB Output is correct
3 Correct 181 ms 29008 KB Output is correct
4 Correct 176 ms 28752 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4824 KB Output is correct
2 Correct 6 ms 4696 KB Output is correct
3 Correct 6 ms 7040 KB Output is correct
4 Correct 5 ms 7004 KB Output is correct
5 Correct 6 ms 6988 KB Output is correct
6 Correct 5 ms 7004 KB Output is correct
7 Correct 80 ms 15444 KB Output is correct
8 Correct 181 ms 28804 KB Output is correct
9 Correct 181 ms 29008 KB Output is correct
10 Correct 176 ms 28752 KB Output is correct
11 Correct 121 ms 20288 KB Output is correct
12 Incorrect 285 ms 33620 KB Output isn't correct
13 Halted 0 ms 0 KB -