oj.uz

Submission #556122

# Submission time Handle Problem Language Result Execution time Memory
556122 2022-05-02T11:50:13 Z Alexandruabcde Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 548 ms 36624 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
constexpr LL INF = 1LL * 1e16;
constexpr int NMAX = 2e5 + 5;

LL val[NMAX];
struct Node {
    LL dp[2][2];
};

LL modul (LL x) {
    if (x < 0) x = -x;
    return x;
}

void CompareBest (LL &x, LL y) {
    x = max(x, y);
}

class SegmentTree {
private:
    vector <Node> arb;
    int sz;

    void Comb (int nod, int a, int b) {
        int st = 2 * nod, dr = 2 * nod + 1;
        int mij = (a + b) / 2;

        for (int caz_st = 0; caz_st < 2; ++ caz_st)
            for (int caz_dr = 0; caz_dr < 2; ++ caz_dr) {
                arb[nod].dp[caz_st][caz_dr] = -INF;

                CompareBest(arb[nod].dp[caz_st][caz_dr], arb[st].dp[caz_st][0] + arb[dr].dp[0][caz_dr]);
                CompareBest(arb[nod].dp[caz_st][caz_dr], arb[st].dp[caz_st][0] + arb[dr].dp[1][caz_dr]);
                CompareBest(arb[nod].dp[caz_st][caz_dr], arb[st].dp[caz_st][1] + arb[dr].dp[0][caz_dr]);

                if (val[mij] * val[mij+1] >= 0)
                    CompareBest(arb[nod].dp[caz_st][caz_dr], arb[st].dp[caz_st][1] + arb[dr].dp[1][caz_dr]);
            }
    }

    void Update (int nod, int a, int b, int poz, LL val) {
        if (a == b) {
            arb[nod].dp[0][0] = 0;
            arb[nod].dp[1][1] = modul(val);
            arb[nod].dp[1][0] = arb[nod].dp[0][1] = -INF;
            return;
        }

        int mij = (a + b) / 2;

        if (poz <= mij) Update(2*nod, a, mij, poz, val);
        else Update(2*nod+1, mij+1, b, poz, val);

        Comb(nod, a, b);
    }

public:
    void Init (int Size) {
        arb.resize(4*Size+4);
        for (int i = 1; i <= 4 * Size; ++ i ) {
            arb[i].dp[0][0] = arb[i].dp[1][1] = 0;
            arb[i].dp[1][0] = arb[i].dp[0][1] = -INF;
        }
        sz = Size;
    }

    void Update (int pos, LL value) {
        Update(1, 1, sz, pos, value);
    }

    LL Best () {
        LL ans = 0;
        CompareBest(ans, arb[1].dp[0][0]);
        CompareBest(ans, arb[1].dp[1][0]);
        CompareBest(ans, arb[1].dp[0][1]);
        CompareBest(ans, arb[1].dp[1][1]);

        return ans;
    }
};

SegmentTree SGT;
int N, Q;

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> Q;

    for (int i = 1; i <= N; ++ i )
        cin >> val[i];

    for (int i = 1; i < N; ++ i )
        val[i] = val[i] - val[i+1];
    val[N] = 0;
    SGT.Init(N-1);

    for (int i = 1; i < N; ++ i )
        SGT.Update(i, val[i]);
}

void Solve () {
    for (; Q; -- Q ) {
        int l, r;
        LL x;
        cin >> l >> r >> x;

        val[l-1] -= x;
        val[r] += x;

        if (l-1 > 0) SGT.Update(l-1, val[l-1]);
        if (r < N) SGT.Update(r, val[r]);

        cout << SGT.Best() << '\n';
    }
}

int main () {
    Read();
    Solve();

    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 4 ms 852 KB Output is correct
8 Correct 5 ms 812 KB Output is correct
9 Correct 5 ms 836 KB Output is correct
10 Correct 6 ms 852 KB Output is correct
11 Correct 5 ms 812 KB Output is correct
12 Correct 5 ms 852 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 4 ms 852 KB Output is correct
8 Correct 5 ms 812 KB Output is correct
9 Correct 5 ms 836 KB Output is correct
10 Correct 6 ms 852 KB Output is correct
11 Correct 5 ms 812 KB Output is correct
12 Correct 5 ms 852 KB Output is correct
13 Correct 459 ms 36008 KB Output is correct
14 Correct 548 ms 36052 KB Output is correct
15 Correct 519 ms 36036 KB Output is correct
16 Correct 544 ms 35884 KB Output is correct
17 Correct 482 ms 35896 KB Output is correct
18 Correct 452 ms 36624 KB Output is correct