Submission #637525

#	Time	Username	Problem	Language	Result	Execution time	Memory
637525		tvladm2009	Simple (info1cup19_simple)	C++14	60 / 100	1067 ms	34964 KiB

subway

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40