oj.uz

Submission #230776

# Submission time Handle Problem Language Result Execution time Memory
230776 2020-05-11T17:14:43 Z andreiomd Simple (info1cup19_simple) C++11
100 / 100
 367 ms 34504 KB 
#include <iostream>
#include <cctype>
#include <cstring>

using namespace std;

const long long INF = 1LL * 1e18;

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

namespace InParser
{
static const int BSIZE = (1 << 16);
static int pos = BSIZE - 1;

char buff[BSIZE];

static inline char Char ()
{
    ++pos;

    if(pos == BSIZE)
    {
        pos = 0;

        memset(buff, 0, sizeof(buff));
        fread(buff, 1, BSIZE, stdin);
    }

    return buff[pos];
}

static inline int Int ()
{
    int r = 0;

    for( ; ; )
    {
        char Ch = Char();

        if(Ch >= '0' && Ch <= '9')
        {
            r = (int)(Ch - '0');

            break;
        }
    }

    for( ; ; )
    {
        char Ch = Char();

        if(Ch >= '0' && Ch <= '9')
            r = r * 10 + (int)(Ch - '0');
        else
            break;
    }

    return r;
}
};

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);

    N = InParser :: Int();

    for(int i = 1; i <= N; ++i)
        X = InParser :: Int(), AINT.Update(1, 1, N, i, i, X);

    return;
}

static inline void TestCase ()
{
    Type = InParser :: Int();
    a = InParser :: Int();
    b = InParser :: Int();

    if(Type == 0)
    {
        Val = InParser :: Int();

        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;

    printf("%lld %lld\n", 1LL * ans.Min_Even, 1LL * ans.Max_Odd);

    return;
}

static inline void Solve ()
{
    Q = InParser :: Int();

    while(Q--)
        TestCase();

    return;
}

int main()
{
    Load();

    Solve();

    return 0;
}

Compilation message

subway.cpp: In function 'char InParser::Char()':
subway.cpp:27:14: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         fread(buff, 1, BSIZE, stdin);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 25600 KB Output is correct
2 Correct 21 ms 25600 KB Output is correct
3 Correct 21 ms 25600 KB Output is correct
4 Correct 24 ms 25856 KB Output is correct
5 Correct 21 ms 25728 KB Output is correct
6 Correct 22 ms 25728 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 28836 KB Output is correct
2 Correct 281 ms 31992 KB Output is correct
3 Correct 279 ms 32248 KB Output is correct
4 Correct 261 ms 31992 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 25600 KB Output is correct
2 Correct 21 ms 25600 KB Output is correct
3 Correct 21 ms 25600 KB Output is correct
4 Correct 24 ms 25856 KB Output is correct
5 Correct 21 ms 25728 KB Output is correct
6 Correct 22 ms 25728 KB Output is correct
7 Correct 135 ms 28836 KB Output is correct
8 Correct 281 ms 31992 KB Output is correct
9 Correct 279 ms 32248 KB Output is correct
10 Correct 261 ms 31992 KB Output is correct
11 Correct 161 ms 29432 KB Output is correct
12 Correct 363 ms 32552 KB Output is correct
13 Correct 344 ms 33784 KB Output is correct
14 Correct 367 ms 32632 KB Output is correct
15 Correct 331 ms 34504 KB Output is correct
16 Correct 66 ms 28536 KB Output is correct