oj.uz

Submission #230769

# Submission time Handle Problem Language Result Execution time Memory
230769 2020-05-11T16:47:57 Z andreiomd Simple (info1cup19_simple) C++11
30 / 100
 396 ms 54776 KB 
#include <iostream>
#include <cstdio>
#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("%I64d %I64d\n", ans.Min_Even, 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 'void TestCase()':
subway.cpp:227:54: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
     printf("%I64d %I64d\n", ans.Min_Even, ans.Max_Odd);
                             ~~~~~~~~~~~~             ^
subway.cpp:227:54: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 25856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 40176 KB Output is correct
2 Correct 396 ms 54648 KB Output is correct
3 Correct 396 ms 54648 KB Output is correct
4 Correct 383 ms 54776 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 25856 KB Output isn't correct
2 Halted 0 ms 0 KB -