oj.uz

Submission #637585

# Submission time Handle Problem Language Result Execution time Memory
637585 2022-09-02T12:44:51 Z tvladm2009 Simple (info1cup19_simple) C++14
100 / 100
 398 ms 40440 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int MAX_N = 2 * 1e5;
const ll INF = (1LL << 60);

int a[MAX_N + 1];

int n, q;

struct Node {
    ll maxEven;
    ll minEven;
    ll maxOdd;
    ll minOdd;

    Node() {
        maxEven = -1;
        minEven = INF;
        maxOdd = -1;
        minOdd = INF;
    }
};

Node aint[4 * MAX_N + 1];
ll lazy[4 * MAX_N + 1];

Node join(Node lson, Node rson) {
    Node aux;
    aux.maxEven = max(lson.maxEven, rson.maxEven);
    aux.minEven = min(lson.minEven, rson.minEven);
    aux.maxOdd = max(lson.maxOdd, rson.maxOdd);
    aux.minOdd = min(lson.minOdd, rson.minOdd);
    return aux;
}

void modify(Node &parent, ll val) {
    if (val & 1) {
        swap(parent.maxEven, parent.maxOdd);
        swap(parent.minEven, parent.minOdd);
    }
    if (parent.maxEven != -1) {
        parent.maxEven += val;
    }
    if (parent.minEven != INF) {
        parent.minEven += val;
    }
    if (parent.maxOdd != -1) {
        parent.maxOdd += val;
    }
    if (parent.minOdd != INF) {
        parent.minOdd += val;
    }
}

void push(int v) {
    if (lazy[v] != 0) {
        lazy[2 * v] += lazy[v];
        modify(aint[2 * v], lazy[v]);
        lazy[2 * v + 1] += lazy[v];
        modify(aint[2 * v + 1], lazy[v]);
        lazy[v] = 0;
    }
}

void build(int v, int l, int r) {
    if (l == r) {
        if (a[l] & 1) {
            aint[v].maxOdd = a[l];
            aint[v].minOdd = a[l];
        } else {
            aint[v].maxEven = a[l];
            aint[v].minEven = a[l];
        }
    } else {
        int mid = (l + r) / 2;
        build(2 * v, l, mid);
        build(2 * v + 1, mid + 1, r);
        aint[v] = join(aint[2 * v], aint[2 * v + 1]);
    }
}

void update(int v, int l, int r, int p, int q, int val) {
    if (p > q) {
        return;
    } else if (p <= l && r <= q) {
        modify(aint[v], val);
        lazy[v] += val;
    } else {
        push(v);
        int mid = (l + r) / 2;
        update(2 * v, l, mid, p, min(mid, q), val);
        update(2 * v + 1, mid + 1, r, max(p, mid + 1), q, val);
        aint[v] = join(aint[2 * v], aint[2 * v + 1]);
    }
}

Node tmp;

Node query(int v, int l, int r, int p, int q) {
    if (p > q) {
        return tmp;
    } else if (p <= l && r <= q) {
        return aint[v];
    } else {
        push(v);
        int mid = (l + r) / 2;
        Node ql = query(2 * v, l, mid, p, min(mid, q));
        Node qr = query(2 * v + 1, mid + 1, r, max(p, mid + 1), q);
        return join(ql, qr);
    }
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    build(1, 1, n);
    cin >> q;
    while (q--) {
        int t, l, r;
        cin >> t >> l >> r;
        if (t == 0) {
            int val;
            cin >> val;
            update(1, 1, n, l, r, val);
        } else {
            Node q = query(1, 1, n, l, r);
            if (q.minEven == INF) {
                cout << "-1 ";
            } else {
                cout << q.minEven << " ";
            }
            cout << q.maxOdd << "\n";
        }
    }

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 25428 KB Output is correct
2 Correct 16 ms 25428 KB Output is correct
3 Correct 16 ms 25580 KB Output is correct
4 Correct 16 ms 25556 KB Output is correct
5 Correct 17 ms 25536 KB Output is correct
6 Correct 17 ms 25592 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 27524 KB Output is correct
2 Correct 263 ms 29604 KB Output is correct
3 Correct 249 ms 29636 KB Output is correct
4 Correct 268 ms 29628 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 25428 KB Output is correct
2 Correct 16 ms 25428 KB Output is correct
3 Correct 16 ms 25580 KB Output is correct
4 Correct 16 ms 25556 KB Output is correct
5 Correct 17 ms 25536 KB Output is correct
6 Correct 17 ms 25592 KB Output is correct
7 Correct 125 ms 27524 KB Output is correct
8 Correct 263 ms 29604 KB Output is correct
9 Correct 249 ms 29636 KB Output is correct
10 Correct 268 ms 29628 KB Output is correct
11 Correct 150 ms 29668 KB Output is correct
12 Correct 381 ms 35356 KB Output is correct
13 Correct 312 ms 39860 KB Output is correct
14 Correct 398 ms 39144 KB Output is correct
15 Correct 293 ms 40440 KB Output is correct
16 Correct 106 ms 32580 KB Output is correct