oj.uz

Submission #1062016

# Submission time Handle Problem Language Result Execution time Memory
1062016 2024-08-16T17:02:16 Z PanosPask Sjeckanje (COCI21_sjeckanje) C++14
55 / 110
 2000 ms 117588 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 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.set(i, D[i]);
    }

    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 function 'int main()':
Main.cpp:124:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |     scanf("%d %d", &N, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:131:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |         scanf("%d", &A[i]);
      |         ~~~~~^~~~~~~~~~~~~
Main.cpp:140:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |         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 2 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 2 ms 348 KB Output is correct
7 Correct 20 ms 2140 KB Output is correct
8 Correct 19 ms 2236 KB Output is correct
9 Correct 19 ms 2140 KB Output is correct
10 Correct 19 ms 2140 KB Output is correct
11 Correct 21 ms 2140 KB Output is correct
12 Correct 18 ms 2140 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 2 ms 348 KB Output is correct
7 Correct 20 ms 2140 KB Output is correct
8 Correct 19 ms 2236 KB Output is correct
9 Correct 19 ms 2140 KB Output is correct
10 Correct 19 ms 2140 KB Output is correct
11 Correct 21 ms 2140 KB Output is correct
12 Correct 18 ms 2140 KB Output is correct
13 Execution timed out 2068 ms 117588 KB Time limit exceeded
14 Halted 0 ms 0 KB -