oj.uz

Submission #637584

# Submission time Handle Problem Language Result Execution time Memory
637584 2022-09-02T12:44:25 Z tvladm2009 Simple (info1cup19_simple) C++14
60 / 100
 1000 ms 31504 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 20 ms 25416 KB Output is correct
2 Correct 19 ms 25504 KB Output is correct
3 Correct 18 ms 25556 KB Output is correct
4 Correct 17 ms 25556 KB Output is correct
5 Correct 17 ms 25556 KB Output is correct
6 Correct 16 ms 25536 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 27476 KB Output is correct
2 Correct 277 ms 29596 KB Output is correct
3 Correct 257 ms 29660 KB Output is correct
4 Correct 277 ms 29612 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 25416 KB Output is correct
2 Correct 19 ms 25504 KB Output is correct
3 Correct 18 ms 25556 KB Output is correct
4 Correct 17 ms 25556 KB Output is correct
5 Correct 17 ms 25556 KB Output is correct
6 Correct 16 ms 25536 KB Output is correct
7 Correct 124 ms 27476 KB Output is correct
8 Correct 277 ms 29596 KB Output is correct
9 Correct 257 ms 29660 KB Output is correct
10 Correct 277 ms 29612 KB Output is correct
11 Correct 529 ms 29712 KB Output is correct
12 Execution timed out 1095 ms 31504 KB Time limit exceeded
13 Halted 0 ms 0 KB -