oj.uz

Submission #637525

# Submission time Handle Problem Language Result Execution time Memory
637525 2022-09-02T11:22:54 Z tvladm2009 Simple (info1cup19_simple) C++14
60 / 100
 1000 ms 34964 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);
            for (int i = l; i <= r; i++) {
                a[i] += 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 17 ms 25428 KB Output is correct
2 Correct 17 ms 25560 KB Output is correct
3 Correct 19 ms 25684 KB Output is correct
4 Correct 16 ms 25652 KB Output is correct
5 Correct 19 ms 25652 KB Output is correct
6 Correct 16 ms 25656 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 27468 KB Output is correct
2 Correct 250 ms 34576 KB Output is correct
3 Correct 261 ms 34580 KB Output is correct
4 Correct 267 ms 34652 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 25428 KB Output is correct
2 Correct 17 ms 25560 KB Output is correct
3 Correct 19 ms 25684 KB Output is correct
4 Correct 16 ms 25652 KB Output is correct
5 Correct 19 ms 25652 KB Output is correct
6 Correct 16 ms 25656 KB Output is correct
7 Correct 123 ms 27468 KB Output is correct
8 Correct 250 ms 34576 KB Output is correct
9 Correct 261 ms 34580 KB Output is correct
10 Correct 267 ms 34652 KB Output is correct
11 Correct 514 ms 32460 KB Output is correct
12 Execution timed out 1067 ms 34964 KB Time limit exceeded
13 Halted 0 ms 0 KB -