Submission #230773

#	Time	Username	Problem	Language	Result	Execution time	Memory
230773		andreiomd	Simple (info1cup19_simple)	C++11	100 / 100	439 ms	34936 KiB

subway

#include <iostream>

using namespace std;

const long long INF = 1LL * 1e18;

int N, X, Q, Type, a, b, Val;

struct NodeT
{
    long long Min_Even, Max_Even, Min_Odd, Max_Odd;

    NodeT ()
    {
        Min_Even = Min_Odd = INF;

        Max_Even = Max_Odd = -INF;
    }
};

class SegmentTree
{
    static const int NMAX = 2e5 + 5;

    NodeT A[(NMAX << 2)];
    long long Lazy[(NMAX << 2)];

    inline void Update_Node (NodeT &X, long long Val)
    {
        if(X.Min_Even == INF && X.Min_Odd == INF)
        {
            if(Val & 1)
                X.Min_Odd = X.Max_Odd = Val;
            else
                X.Min_Even = X.Max_Even = Val;

            return;
        }

        if(Val & 1)
        {
            swap(X.Min_Even, X.Min_Odd);

            swap(X.Max_Even, X.Max_Odd);
        }

        if(X.Min_Even != INF)
            X.Min_Even += 1LL * Val, X.Max_Even += 1LL * Val;

        if(X.Min_Odd != INF)
            X.Min_Odd += 1LL * Val, X.Max_Odd += 1LL * Val;

        return;
    }

    inline void Go (int Node, int a, int b)
    {
        if(a == b)
            return;

        if(!Lazy[Node])
            return;

        Update_Node(A[2 * Node], Lazy[Node]);
        Update_Node(A[2 * Node + 1], Lazy[Node]);

        Lazy[2 * Node] += Lazy[Node];
        Lazy[2 * Node + 1] += Lazy[Node];

        Lazy[Node] = 0;

        return;
    }

    inline NodeT Merge (NodeT X, NodeT Y)
    {
        NodeT ans;

        ans.Min_Even = min(X.Min_Even, Y.Min_Even);
        ans.Max_Even = max(X.Max_Even, Y.Max_Even);

        ans.Min_Odd = min(X.Min_Odd, Y.Min_Odd);
        ans.Max_Odd = max(X.Max_Odd, Y.Max_Odd);

        return ans;
    }

public:
    inline void Update (int Node, int a, int b, int ua, int ub, int Val)
    {
        if(ua <= a && b <= ub)
        {
            Lazy[Node] += 1LL * Val;

            Update_Node(A[Node], Val);

            return;
        }

        Go(Node, a, b);

        int Mid = (a + b) >> 1;

        if(ua <= Mid)
            Update(2 * Node, a, Mid, ua, ub, Val);

        if(ub > Mid)
            Update(2 * Node + 1, Mid + 1, b, ua, ub, Val);

        A[Node] = Merge(A[2 * Node], A[2 * Node + 1]);

        return;
    }

    inline NodeT Query (int Node, int a, int b, int qa, int qb)
    {
        if(qa <= a && b <= qb)
            return A[Node];

        Go(Node, a, b);

        int Mid = (a + b) >> 1;

        NodeT p1, p2;

        if(qa <= Mid)
            p1 = Query(2 * Node, a, Mid, qa, qb);

        if(qb > Mid)
            p2 = Query(2 * Node + 1, Mid + 1, b, qa, qb);

        return Merge(p1, p2);
    }
} AINT;

static inline void Load ()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

    for(int i = 1; i <= N; ++i)
        cin >> X, AINT.Update(1, 1, N, i, i, X);

    return;
}

static inline void TestCase ()
{
    cin >> Type >> a >> b;

    if(Type == 0)
    {
        cin >> Val;

        AINT.Update(1, 1, N, a, b, Val);

        return;
    }

    NodeT ans = AINT.Query(1, 1, N, a, b);

    if(ans.Min_Even == INF)
        ans.Min_Even = -1;

    if(ans.Max_Odd == -INF)
        ans.Max_Odd = -1;

    cout << ans.Min_Even << ' ' << ans.Max_Odd << '\n';

    return;
}

static inline void Solve ()
{
    cin >> Q;

    while(Q--)
        TestCase();

    return;
}

int main()
{
    Load();

    Solve();

    return 0;
}

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