Submission #691584

#	Time	Username	Problem	Language	Result	Execution time	Memory
691584		LucaLucaM	Simple (info1cup19_simple)	C++17	100 / 100	392 ms	31108 KiB

subway

#include <bits/stdc++.h>

using namespace std;

#define int long long 

struct node
{
    int pmin, pmax, imin, imax, lazy;

    node()
    {
        pmin = pmax = imin = imax = -1;
        lazy = 0;
    }

    void operator = (vector<int>v)
    {
        pmin = v[0], pmax = v[1], imin = v[2], imax = v[3], lazy = v[4];
    }
};

node operator + (node a, node b)
{
    node ans;

    if (a.pmin == -1)
        ans.pmin = b.pmin;
    else if (b.pmin == -1)
        ans.pmin = a.pmin;
    else
        ans.pmin = min(a.pmin, b.pmin);

    if (a.pmax == -1)
        ans.pmax = b.pmax;
    else if (b.pmax == -1)
        ans.pmax = a.pmax;
    else
        ans.pmax = max(a.pmax, b.pmax);

    if (a.imin == -1)
        ans.imin = b.imin;
    else if (b.imin == -1)
        ans.imin = a.imin;
    else
        ans.imin = min(a.imin, b.imin);

    if (a.imax == -1)
        ans.imax = b.imax;
    else if (b.imax == -1)
        ans.imax = a.imax;
    else
        ans.imax = max(a.imax, b.imax);

    return ans;
}


class ST
{
protected:
    int n;
    vector<node>a;
public:
    void init (int N)
    {
        n = 1;
        while (n < N)
            n <<= 1;
        n <<= 1;
        n++;
        a.resize(n);
    }

    void propagate (int nod, int st, int dr)
    {
        if (a[nod].lazy)
        {
            int lazy = a[nod].lazy;

            if (lazy % 2 == 0)
            {
                if (a[nod].pmin != -1)
                {
                    a[nod].pmin += lazy;
                    a[nod].pmax += lazy;
                }

                if (a[nod].imin != -1)
                {
                    a[nod].imin += lazy;
                    a[nod].imax += lazy;
                }
            }
            else
            {
                int pmin = a[nod].pmin, pmax = a[nod].pmax;
                int imin = a[nod].imin, imax = a[nod].imax;

                if (pmin != -1)
                {
                    a[nod].imin = pmin + lazy;
                    a[nod].imax = pmax + lazy;
                }
                else
                    a[nod].imin = a[nod].imax = -1;

                if (imin != -1)
                {
                    a[nod].pmin = imin + lazy;
                    a[nod].pmax = imax + lazy;
                }
                else
                    a[nod].pmin = a[nod].pmax = -1;
            }

            if (st != dr)
            {
                a[2*nod].lazy += a[nod].lazy;
                a[2*nod+1].lazy += a[nod].lazy;
            }

            a[nod].lazy = 0;
        }
    }

    void build (int nod, int st, int dr)
    {
        if (st == dr)
        {
            int x;
            cin >> x;

            if (x % 2 == 0)
                a[nod] = {x, x, -1, -1, 0};
            else
                a[nod] = {-1, -1, x, x, 0};
        }
        else
        {
            int mid = (st + dr) / 2;

            build(2*nod, st, mid);
            build(2*nod+1, mid+1, dr);

            a[nod] = a[2*nod] + a[2*nod+1];
        }
    }

    void update (int nod, int st, int dr, int l, int r, int x)
    {
        propagate(nod, st, dr);

        if (l <= st && dr <= r)
            a[nod].lazy += x;
        else
        {
            int mid = (st + dr) / 2;

            if (l <= mid)
                update(2*nod, st, mid, l, r, x);
            if (mid < r)
                update(2*nod+1, mid+1, dr, l, r, x);

            propagate(2*nod, st, mid);
            propagate(2*nod+1, mid+1, dr);

            a[nod] = a[2*nod] + a[2*nod+1];
        }
    }

    node query (int nod, int st, int dr, int l, int r)
    {
        propagate(nod, st, dr);
        if (l <= st && dr <= r)
            return a[nod];
        int mid = (st + dr) / 2;

        if (l <= mid && mid < r)
        {
            node ls = query(2*nod, st, mid, l, r);
            node rs = query(2*nod+1, mid+1, dr, l, r);

            return ls + rs;
        }
        if (l <= mid)
        {
            return query(2*nod, st, mid, l, r);
        }
        if (mid < r)
        {
            return query(2*nod+1, mid+1, dr, l, r);
        }
    }
};

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

    int n;
    cin >> n;

    ST a;

    a.init(n);
    a.build(1, 1, n);

    int q;
    cin >> q;

    while (q--)
    {
        int op;
        cin >> op;

        if (op == 0)
        {
            int x, y, val;
            cin >> x >> y >> val;

            a.update(1, 1, n, x, y, val);
        }
        else
        {
            //cout << a[2].pmin << ' ' << a[3].pmin << ' ' << a[4].pmin << '\n';
            int x, y;
            cin >> x >> y;

            node ans = a.query(1, 1, n, x, y);

            cout << ans.pmin << ' ' << ans.imax << '\n';
        }
    }

    return 0;
}

Compilation message (stderr)

subway.cpp: In member function 'node ST::query(long long int, long long int, long long int, long long int, long long int)':
subway.cpp:194:5: warning: control reaches end of non-void function [-Wreturn-type]
  194 |     }
      |     ^

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