oj.uz

Submission #915715

# Submission time Handle Problem Language Result Execution time Memory
915715 2024-01-24T15:25:29 Z Bubu_Orange Simple (info1cup19_simple) C++14
60 / 100
 315 ms 34036 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].mxp=v[left];
        }else{
            tree[node].mni=v[left];
            tree[node].mnp=LONG_LONG_MAX;
            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!=LONG_LONG_MAX){
        tree[node].mnp+=lazy[node];
    }
    if(tree[node].mxi!=0){
        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(a<=left&&right<=b){
        lazy[node]+=val;
        update_lazy(node, left, right);
        return;
    }
    long long mid=(left+right)/2;
    if(a<=mid){
        update(2*node, left, mid, a, b, val);
    }
    if(b>=mid+1){
        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);
    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=0;
            query(1, 1, n, A, B);
            if(mn==LONG_LONG_MAX){
                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 4804 KB Output is correct
2 Correct 4 ms 4696 KB Output is correct
3 Correct 6 ms 6872 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 7000 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 15688 KB Output is correct
2 Correct 212 ms 28984 KB Output is correct
3 Correct 198 ms 28900 KB Output is correct
4 Correct 216 ms 28880 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4804 KB Output is correct
2 Correct 4 ms 4696 KB Output is correct
3 Correct 6 ms 6872 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 7000 KB Output is correct
7 Correct 90 ms 15688 KB Output is correct
8 Correct 212 ms 28984 KB Output is correct
9 Correct 198 ms 28900 KB Output is correct
10 Correct 216 ms 28880 KB Output is correct
11 Correct 135 ms 20296 KB Output is correct
12 Incorrect 315 ms 34036 KB Output isn't correct
13 Halted 0 ms 0 KB -