Submission #915745

#	Time	Username	Problem	Language	Result	Execution time	Memory
915745		Bubu_Orange	Simple (info1cup19_simple)	C++14	60 / 100	285 ms	33620 KiB

subway

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40