Submission #230369

#	Time	Username	Problem	Language	Result	Execution time	Memory
230369		Alexandruabcde	Simple (info1cup19_simple)	C++14	100 / 100	436 ms	31096 KiB

subway

#include <iostream>
#define INF 1000000000000000

using namespace std;

constexpr int NMAX = 200005;

struct arbore
{
    long long MinPar, MinImpar, MaxPar, MaxImpar;
};

arbore arb[4*NMAX];
long long lazy[4*NMAX];

int N;

void upgradez (int nod, long long val)
{
    lazy[nod] += val;

    if (arb[nod].MinPar != INF)
        arb[nod].MinPar += val;
    if (arb[nod].MinImpar != INF)
        arb[nod].MinImpar += val;
    if (arb[nod].MaxPar != -INF)
        arb[nod].MaxPar += val;
    if (arb[nod].MaxImpar != -INF)
        arb[nod].MaxImpar += val;

    if (val % 2 == 1)
    {
        swap(arb[nod].MinPar, arb[nod].MinImpar);

        swap(arb[nod].MaxPar, arb[nod].MaxImpar);
    }
}

void Propag (int nod, int a, int b)
{
    if (a == b || lazy[nod] == 0) return;

    lazy[2*nod] += lazy[nod];
    lazy[2*nod+1] += lazy[nod];

    if (arb[2*nod].MinPar != INF)
        arb[2*nod].MinPar += lazy[nod];
    if (arb[2*nod+1].MinPar != INF)
        arb[2*nod+1].MinPar += lazy[nod];

    if (arb[2*nod].MaxPar != -INF)
        arb[2*nod].MaxPar += lazy[nod];
    if (arb[2*nod+1].MaxPar != -INF)
        arb[2*nod+1].MaxPar += lazy[nod];

    if (arb[2*nod].MinImpar != INF)
        arb[2*nod].MinImpar += lazy[nod];
    if (arb[2*nod+1].MinImpar != INF)
        arb[2*nod+1].MinImpar += lazy[nod];

    if (arb[2*nod].MaxImpar != -INF)
        arb[2*nod].MaxImpar += lazy[nod];
    if (arb[2*nod+1].MaxImpar != -INF)
        arb[2*nod+1].MaxImpar += lazy[nod];

    if (lazy[nod] % 2 == 1)
    {
        swap(arb[2*nod].MaxPar, arb[2*nod].MaxImpar);
        swap(arb[2*nod].MinPar, arb[2*nod].MinImpar);
        swap(arb[2*nod+1].MaxPar, arb[2*nod+1].MaxImpar);
        swap(arb[2*nod+1].MinPar, arb[2*nod+1].MinImpar);
    }

    lazy[nod] = 0;
}

void Update_Lazy (int nod, int a, int b, int ua, int ub, long long val)
{
    if (ua <= a && b <= ub)
    {
        upgradez(nod, val);

        return;
    }

    Propag(nod, a, b);

    int mij = (a + b) / 2;

    if (ua <= mij) Update_Lazy(2*nod, a, mij, ua, ub, val);
    if (mij < ub) Update_Lazy(2*nod+1, mij+1, b, ua, ub, val);

    arb[nod].MaxPar = max(arb[2*nod].MaxPar, arb[2*nod+1].MaxPar);
    arb[nod].MaxImpar = max(arb[2*nod].MaxImpar, arb[2*nod+1].MaxImpar);
    arb[nod].MinPar = min(arb[2*nod].MinPar, arb[2*nod+1].MinPar);
    arb[nod].MinImpar = min(arb[2*nod].MinImpar, arb[2*nod+1].MinImpar);
}

void Update_Single (int nod, int a, int b, int poz, long long val)
{
    if (a == b)
    {
        if (val % 2 == 0)
        {
            arb[nod].MaxPar = arb[nod].MinPar = val;
            arb[nod].MinImpar = INF;
            arb[nod].MaxImpar = -INF;
        }
        else
        {
            arb[nod].MaxImpar = arb[nod].MinImpar = val;
            arb[nod].MinPar = INF;
            arb[nod].MaxPar = -INF;
        }

        return;
    }

    int mij = (a + b) / 2;

    if (poz <= mij) Update_Single(2*nod, a, mij, poz, val);
    else Update_Single(2*nod+1, mij+1, b, poz, val);

    arb[nod].MaxPar = max(arb[2*nod].MaxPar, arb[2*nod+1].MaxPar);
    arb[nod].MaxImpar = max(arb[2*nod].MaxImpar, arb[2*nod+1].MaxImpar);
    arb[nod].MinPar = min(arb[2*nod].MinPar, arb[2*nod+1].MinPar);
    arb[nod].MinImpar = min(arb[2*nod].MinImpar, arb[2*nod+1].MinImpar);
}

pair <long long, long long> Query (int nod, int a, int b, int qa, int qb)
{
    if (qa <= a && b <= qb)
    {
        return {arb[nod].MinPar, arb[nod].MaxImpar};
    }

    Propag(nod, a, b);

    int mij = (a + b) / 2;
    pair <long long, long long> ans_1 = {INF, -INF}, ans_2 = {INF, -INF};

    if (qa <= mij) ans_1 = Query(2*nod, a, mij, qa, qb);
    if (mij < qb) ans_2 = Query(2*nod+1, mij+1, b, qa, qb);

    return {min(ans_1.first, ans_2.first), max(ans_1.second, ans_2.second)};
}

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

    int Q;

    cin >> N;

    for (int i = 1; i <= N; ++i)
    {
        long long x;

        cin >> x;

        Update_Single(1, 1, N, i, x);
    }

    cin >> Q;

    for (; Q; --Q)
    {
        int type;

        cin >> type;

        if (type == 0)
        {
            int a, b;
            long long val;

            cin >> a >> b >> val;

            Update_Lazy(1, 1, N, a, b, val);
        }
        else
        {
            int a, b;

            cin >> a >> b;

            pair <long long, long long> x = Query(1, 1, N, a, b);

            if (x.first == INF) x.first = -1;
            if (x.second == -INF) x.second = -1;

            cout << x.first << " " << x.second << '\n';
        }
    }
    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40