Submission #990173

#	Time	Username	Problem	Language	Result	Execution time	Memory
990173		VMaksimoski008	Simple (info1cup19_simple)	C++17	100 / 100	229 ms	43332 KiB

subway

#include <bits/stdc++.h>

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;
const double eps = 1e-9;

struct Node {
    ll mnO, mnE, mxO, mxE;
};

Node merge(Node a, Node b) {
    Node res;

    res.mnO = min(a.mnO, b.mnO);
    res.mnE = min(a.mnE, b.mnE);
    res.mxO = max(a.mxO, b.mxO);
    res.mxE = max(a.mxE, b.mxE);

    return res;
}

Node shit() {
    Node res;
    res.mnO = res.mnE = 1e15;
    res.mxO = res.mxE = -1e15;
    return res;
}

struct SegTree {
    int n;
    vector<Node> tree;
    vector<ll> lazy;
    vector<int> v;

    SegTree(vector<int> _v) {
        v = _v;
        n = v.size();
        tree.resize(4*n+5);
        lazy.resize(4*n+5);
        build(1, 0, n-1);
    }

    void build(int u, int tl, int tr) {
        if(tl == tr) {
            if(v[tl] % 2 == 0) {
                tree[u].mnE = tree[u].mxE = v[tl];
                tree[u].mnO = 1e15+1;
                tree[u].mxO = -1e15+1;
            } else {
                tree[u].mnO = tree[u].mxO = v[tl];
                tree[u].mnE = 1e15;
                tree[u].mxE = -1e15;
            }
        } else {
            int tm = (tl + tr) / 2;
            build(2*u, tl, tm);
            build(2*u+1, tm+1, tr);
            tree[u] = merge(tree[2*u], tree[2*u+1]);
        }
        //cout << tl << " " << tr << ": " << tree[u].mnO << ", " << tree[u].mxO << " , " << tree[u].mnE << " " << tree[u].mxE << '\n';
    }

    void push(int u, int tl, int tr) {
        if(!lazy[u]) return ;

        if(lazy[u] % 2 == 0) {
            //cout << tl << " " << tr << ": " << lazy[u] << '\n';
            tree[u].mnE += lazy[u];
            tree[u].mnO += lazy[u];
            tree[u].mxO += lazy[u];
            tree[u].mxE += lazy[u];
        } else {
            tree[u].mnE += lazy[u];
            tree[u].mnO += lazy[u];
            tree[u].mxO += lazy[u];
            tree[u].mxE += lazy[u];

            swap(tree[u].mnO, tree[u].mnE);
            swap(tree[u].mxO, tree[u].mxE);

        }

        if(tl != tr) {
            lazy[2*u] += lazy[u];
            lazy[2*u+1] += lazy[u];
        }

        lazy[u] = 0;
    }

    void update(int u, int tl, int tr, int l, int r, int v) {
        push(u, tl, tr);
        if(tl > tr || l > tr || tl > r) return ;

        if(l <= tl && tr <= r) {
            lazy[u] += v;
            push(u, tl, tr);
            return ;
        }

        int tm = (tl + tr) / 2;
        update(2*u, tl, tm, l, r, v);
        update(2*u+1, tm+1, tr, l, r, v);
        tree[u] = merge(tree[2*u], tree[2*u+1]);
    }

    Node query(int u, int tl, int tr, int l, int r) {
        if(tl > tr || l > tr || tl > r) return shit();
        push(u, tl, tr);
        if(l <= tl && tr <= r) return tree[u];
        int tm = (tl + tr) / 2;
        return merge(
            query(2*u, tl, tm, l, r),
            query(2*u+1, tm+1, tr, l, r)
        );
    }

    void update(int l, int r, int v) { update(1, 0, n-1, l, r, v); }

    pll query(int l, int r) {
        Node res = query(1, 0, n-1, l, r);
        return make_pair( res.mnE, res.mxO );
    }
};

int32_t main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int n;
    cin >> n;

    vector<int> v(n);
    for(int &x : v) cin >> x;

    SegTree tree(v);

    int q;
    cin >> q;

    while(q--) {
        int t;
        cin >> t;

        if(t == 0) {
            int l, r, val;
            cin >> l >> r >> val;
            tree.update(l-1, r-1, val);
        } else {
            int l, r;
            cin >> l >> r;
            auto [a, b] = tree.query(l-1, r-1);
            cout << ( (a < 0 || a >= 1e15) ? -1 : a ) << " " << ( (b < 0 || b >= 1e15) ? -1 : b ) << '\n';
        }
    }

    return 0;
}

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