oj.uz

Submission #1062017

# Submission time Handle Problem Language Result Execution time Memory
1062017 2024-08-16T17:06:22 Z PanosPask Sjeckanje (COCI21_sjeckanje) C++14
55 / 110
 2000 ms 112552 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = 1e18;

struct SegTree {
    struct Node {
        /* ans[l][r]:
         * The maximum answer for this segment
         *
         * l and r are boolean variables denoting if we include the leftmost and rightmost elements
         * respectively
         */
        vector<vector<ll>> ans;

        vector<ll> sign;

        Node(void) {
            ans.assign(2, vector<ll>(2, 0));
            sign.assign(2, 0);
        }
    };

    Node DEFAULT;
    int size;
    vector<Node> tree;

    Node merge(const Node& a, const Node& b)
    {
        Node res;

        res.sign[0] = a.sign[0];
        res.sign[1] = b.sign[1];
        if (a.sign[1] == b.sign[0] || a.sign[1] == 0 || b.sign[0] == 0) {
            // We can merge

            for (int l = 0; l < 2; l++) {
                for (int r = 0; r < 2; r++) {
                    res.ans[l][r] = a.ans[l][1] + b.ans[1][r];
                }
            }
        }
        else {
            for (int l = 0; l < 2; l++) {
                for (int r = 0; r < 2; r++) {
                    res.ans[l][r] = max(a.ans[l][1] + b.ans[0][r], a.ans[l][0] + b.ans[1][r]);
                }
            }
        }

        return res;
    }

    int val(int v) {
        if (v < 0) {
            return -1;
        }
        if (v > 0) {
            return 1;
        }

        return 0;
    }

    void init(int N) {
        size = 1;
        while (size < N) {
            size *= 2;
        }

        tree.assign(2 * size, Node());
    }

    void build(vector<ll>& a, int x, int lx, int rx) {
        if (lx == rx - 1) {
            if (lx < a.size()) {
                tree[x].ans[1][1] = abs(a[lx]);
                tree[x].sign[0] = tree[x].sign[1] = val(a[lx]);
            }

            return;
        }

        int mid = (lx + rx) / 2;
        build(a, 2 * x + 1, lx, mid);
        build(a, 2 * x + 2, mid, rx);

        tree[x] = merge(tree[2 * x + 1], tree[2 * x + 2]);
    }
    void build(vector<ll>& a) {
        return build(a, 0, 0, size);
    }

    void set(int i, ll v, int x, int lx, int rx) {
        if (lx == rx - 1) {
            tree[x].ans[1][1] = abs(v);
            tree[x].sign[0] = tree[x].sign[1] = val(v);
            return;
        }

        int mid = (lx + rx) / 2;
        if (i < mid) {
            set(i, v, 2 * x + 1, lx, mid);
        }
        else {
            set(i, v, 2 * x + 2, mid, rx);
        }

        tree[x] = merge(tree[2 * x + 1], tree[2 * x + 2]);
    }
    void set(int i, ll v) {
        set(i, v, 0, 0, size);
    }

    Node calc(int l, int r, int x, int lx, int rx) {
        if (l >= rx || lx >= r) {
            return Node();
        }
        else if (l <= lx && rx <= r) {
            return tree[x];
        }

        int mid = (lx + rx) / 2;
        Node n1 = calc(l, r, 2 * x + 1, lx, mid);
        Node n2 = calc(l, r, 2 * x + 2, mid, rx);

        return merge(n1, n2);
    }
    ll calc(int l, int r) {
        return calc(l, r, 0, 0, size).ans[1][1];
    }
};

int N, Q;
SegTree st;
vector<int> A;
vector<ll> D;

int main(void)
{
    scanf("%d %d", &N, &Q);

    A.resize(N);
    st.init(N - 1);
    D.resize(N - 1);

    for (int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
    }
    for (int i = 0; i < N - 1; i++) {
        D[i] = A[i + 1] - A[i];
    }
    st.build(D);

    while (Q--) {
        int l, r, x;
        scanf("%d %d %d", &l, &r, &x);
        l--; l--;
        r--;

        if (l >= 0) {
            D[l] += x;
            st.set(l, D[l]);
        }
        if (r < N - 1) {
            D[r] -= x;
            st.set(r, D[r]);
        }

        printf("%lld\n", st.calc(0, N - 1));
    }

    return 0;
}

Compilation message

Main.cpp: In member function 'void SegTree::build(std::vector<long long int>&, int, int, int)':
Main.cpp:79:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |             if (lx < a.size()) {
      |                 ~~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:144:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |     scanf("%d %d", &N, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:151:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |         scanf("%d", &A[i]);
      |         ~~~~~^~~~~~~~~~~~~
Main.cpp:160:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |         scanf("%d %d %d", &l, &r, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 16 ms 2140 KB Output is correct
8 Correct 19 ms 2168 KB Output is correct
9 Correct 16 ms 2140 KB Output is correct
10 Correct 15 ms 2140 KB Output is correct
11 Correct 18 ms 2140 KB Output is correct
12 Correct 15 ms 2160 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 16 ms 2140 KB Output is correct
8 Correct 19 ms 2168 KB Output is correct
9 Correct 16 ms 2140 KB Output is correct
10 Correct 15 ms 2140 KB Output is correct
11 Correct 18 ms 2140 KB Output is correct
12 Correct 15 ms 2160 KB Output is correct
13 Execution timed out 2045 ms 112552 KB Time limit exceeded
14 Halted 0 ms 0 KB -