Submission #691584

# Submission time Handle Problem Language Result Execution time Memory
691584 2023-01-31T09:46:15 Z LucaLucaM Simple (info1cup19_simple) C++17
100 / 100
392 ms 31108 KB
#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

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 |     }
      |     ^
# Verdict Execution time Memory Grader output
1 Correct 5 ms 596 KB Output is correct
2 Correct 8 ms 724 KB Output is correct
3 Correct 7 ms 1108 KB Output is correct
4 Correct 7 ms 1108 KB Output is correct
5 Correct 7 ms 1172 KB Output is correct
6 Correct 6 ms 1084 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 121 ms 12276 KB Output is correct
2 Correct 264 ms 24256 KB Output is correct
3 Correct 269 ms 24328 KB Output is correct
4 Correct 239 ms 24284 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 5 ms 596 KB Output is correct
2 Correct 8 ms 724 KB Output is correct
3 Correct 7 ms 1108 KB Output is correct
4 Correct 7 ms 1108 KB Output is correct
5 Correct 7 ms 1172 KB Output is correct
6 Correct 6 ms 1084 KB Output is correct
7 Correct 121 ms 12276 KB Output is correct
8 Correct 264 ms 24256 KB Output is correct
9 Correct 269 ms 24328 KB Output is correct
10 Correct 239 ms 24284 KB Output is correct
11 Correct 204 ms 15152 KB Output is correct
12 Correct 370 ms 29780 KB Output is correct
13 Correct 326 ms 30540 KB Output is correct
14 Correct 392 ms 29720 KB Output is correct
15 Correct 291 ms 31108 KB Output is correct
16 Correct 103 ms 27340 KB Output is correct