Submission #690930

#	Time	Username	Problem	Language	Result	Execution time	Memory
690930		divad	Simple (info1cup19_simple)	C++14	100 / 100	307 ms	41776 KiB

subway

#include <iostream>
#define int long long
#define lc (nod<<1)
#define rc ((nod<<1)|1)
#define INF (1ULL<<60)
#define MAX 200002
using namespace std;
int n,q,t,x,y,v,mini,maxi;

struct Nod{
    int maximp = -1;
    int minimp = INF;
    int maxpar = -1;
    int minpar = INF;
    int lazy;
} aint[4*MAX];

void merge(int nod){
    aint[nod].maximp = max(aint[lc].maximp, aint[rc].maximp);
    aint[nod].minimp = min(aint[lc].minimp, aint[rc].minimp);
    aint[nod].maxpar = max(aint[lc].maxpar, aint[rc].maxpar);
    aint[nod].minpar = min(aint[lc].minpar, aint[rc].minpar);
}

void change(int nod, int val){
    if(aint[nod].maximp != -1){
        aint[nod].maximp += val;
        aint[nod].minimp += val;
    }
    if(aint[nod].maxpar != -1){
        aint[nod].maxpar += val;
        aint[nod].minpar += val;
    }
    if(val%2 == 0){
    }else{
        swap(aint[nod].maxpar, aint[nod].maximp);
        swap(aint[nod].minpar, aint[nod].minimp);
    }
}

void propag(int nod){
    if(aint[nod].lazy != 0){
        aint[lc].lazy += aint[nod].lazy;
        change(lc, aint[nod].lazy);
        aint[rc].lazy += aint[nod].lazy;
        change(rc, aint[nod].lazy);
        aint[nod].lazy = 0;
    }
}

void build(int nod, int st, int dr){
    if(st == dr){
        cin >> x;
        if(x%2 == 0){
            aint[nod].maxpar = aint[nod].minpar = x;
        }else{
            aint[nod].maximp = aint[nod].minimp = x;
        }
    }else{
        int mid = ((st+dr)>>1);
        build(lc, st, mid);
        build(rc, mid+1, dr);
        merge(nod);
    }
}

void update(int nod, int st, int dr, int a, int b, int val){
    /// v[a..b] += val
    if(a <= st && dr <= b){
        aint[nod].lazy += val;
        change(nod, val);
    }else{
        propag(nod);
        int mid = ((st+dr)>>1);
        if(a <= mid){
            update(lc, st, mid, a, b, val);
        }
        if(b >= mid+1){
            update(rc, mid+1, dr, a, b, val);
        }
        merge(nod);
    }
}

void query(int nod, int st, int dr, int a, int b){
    /// maxim impar si minim par din [a..b]
    if(a <= st && dr <= b){
        maxi = max(maxi, aint[nod].maximp);
        mini = min(mini, aint[nod].minpar);
    }else{
        propag(nod);
        int mid = ((st+dr)>>1);
        if(a <= mid){
            query(lc, st, mid, a, b);
        }
        if(b >= mid+1){
            query(rc, mid+1, dr, a, b);
        }
        merge(nod);
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    build(1, 1, n);
    cin >> q;
    while(q--){
        cin >> t >> x >> y;
        if(t == 0){
            cin >> v;
            update(1, 1, n, x, y, v);
        }else{
            mini = INF;
            maxi = -1;
            query(1, 1, n, x, y);
            cout << (mini == INF ? -1 : mini) << " " << maxi << "\n";
        }
    }
    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40