oj.uz

Submission #990173

# Submission time Handle Problem Language Result Execution time Memory
990173 2024-05-29T18:27:25 Z VMaksimoski008 Simple (info1cup19_simple) C++17
100 / 100
 229 ms 43332 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1116 KB Output is correct
2 Correct 4 ms 1116 KB Output is correct
3 Correct 4 ms 1372 KB Output is correct
4 Correct 4 ms 1372 KB Output is correct
5 Correct 4 ms 1372 KB Output is correct
6 Correct 4 ms 1500 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 20936 KB Output is correct
2 Correct 176 ms 41796 KB Output is correct
3 Correct 174 ms 41700 KB Output is correct
4 Correct 186 ms 41792 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1116 KB Output is correct
2 Correct 4 ms 1116 KB Output is correct
3 Correct 4 ms 1372 KB Output is correct
4 Correct 4 ms 1372 KB Output is correct
5 Correct 4 ms 1372 KB Output is correct
6 Correct 4 ms 1500 KB Output is correct
7 Correct 80 ms 20936 KB Output is correct
8 Correct 176 ms 41796 KB Output is correct
9 Correct 174 ms 41700 KB Output is correct
10 Correct 186 ms 41792 KB Output is correct
11 Correct 96 ms 21312 KB Output is correct
12 Correct 229 ms 42304 KB Output is correct
13 Correct 206 ms 43068 KB Output is correct
14 Correct 224 ms 42308 KB Output is correct
15 Correct 190 ms 43332 KB Output is correct
16 Correct 57 ms 39736 KB Output is correct