oj.uz

Submission #838231

# Submission time Handle Problem Language Result Execution time Memory
838231 2023-08-26T11:39:49 Z abysmal Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 231 ms 33688 KB 
#include<iostream>
#include<stdio.h>
#include<stdint.h>
#include<iomanip>
#include<algorithm>
#include<utility>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<deque>
#include<math.h>
#include<assert.h>
#include<string.h>

using namespace std;

const int64_t INF = (int64_t) 1e18 + 100;
const int64_t mINF = (int64_t) 1e6 * 2 + 100;
const int64_t MOD = 1e9 + 7;
const int64_t MOD2 = 998244353;
const int nbit = 31;
const int ndig = 10;
const int nchar = 26;
const int D = 4;
int dr[D] = {-1, 0, 1, 0};
int dc[D] = {0, 1, 0, -1};
const int Dk = 8;
int drk[Dk] = {2, 2, -2, -2, 1, 1, -1, -1};
int dck[Dk] = {1, -1, 1, -1, 2, -2, 2, -2};

struct Node
{
    int l; int r;
    int64_t ar; int64_t ab;
    int64_t lb; int64_t lr;

    Node(int l_, int r_, int64_t ar_, int64_t ab_, int64_t lb_, int64_t lr_) : l(l_), r(r_), ar(ar_), ab(ab_), lb(lb_), lr(lr_) {}
};

struct Solution
{
    int n;
    int q;
    int k;
    vector<int64_t> a;
    vector<int64_t> d;
    vector<Node> tree;
    Solution() {}

    void solve()
    {
        cin >> n >> q;
        a.resize(n, 0);
        d.resize(n, 0);
        for(int i = 0; i < n; i++)
        {
            cin >> a[i];
        }

        k = n;
        while(__builtin_popcount(k) != 1) k++;
        tree.resize(2 * k, Node(0, 0, 0, 0, 0, 0));
        for(int i = 1; i < n; i++)
        {
            d[i] = a[i] - a[i - 1];
            tree[k + i] = Node(d[i], d[i], 0, 0, 0, Abs(d[i]));
        }

        for(int i = k - 1; i >= 1; i--)
        {
            tree[i] = combine(tree[i * 2], tree[i * 2 + 1]);
        }

        for(int i = 0; i < q; i++)
        {
            int l;
            int r;
            int x;
            cin >> l >> r >> x;
            l--; r--;

            if(l != 0) update(l, x);
            if(r + 1 < n) update(r + 1, -x);
            int64_t ans = max({tree[1].ab, tree[1].ar, tree[1].lb, tree[1].lr});
            cout << ans << "\n";
        }
    }

    void update(int i, int val)
    {
        tree[k + i].l += val;
        tree[k + i].r += val;
        tree[k + i].lr = Abs(tree[k + i].l);

        for(int j = (k + i) / 2; j >= 1; j /= 2)
        {
            tree[j] = combine(tree[j * 2], tree[j * 2 + 1]);
        }
    }

    Node combine(Node& left, Node& right)
    {
        Node now(left.l, right.r, 0, 0, 0, 0);

        if(1LL * left.r * right.l >= 0)
        {
            now.lr = left.lr + right.lr;
            now.ar = left.ar + right.lr;
            now.lb = left.lr + right.lb;
            now.ab = left.ar + right.lb;
        }
        else
        {
            now.lr = max(left.lr + right.ar, left.lb + right.lr);
            now.ar = max(left.ar + right.ar, left.ab + right.lr);
            now.lb = max(left.lr + right.ab, left.lb + right.lb);
            now.ab = max(left.ar + right.ab, left.ab + right.lb);
        }

        return now;
    }

    void modadd(int& t1, int t2)
    {
        t1 += t2;
        if(t1 >= MOD) t1-= MOD;
        return;
    }

    void modsub(int& t1, int t2)
    {
        t1 -= t2;
        if(t1 < 0) t1 += MOD;
        return;
    }

    int modmul(int t1, int t2)
    {
        int64_t res = 1LL * t1 * t2;
        return res % MOD;
    }

    int Abs(int tmp)
    {
        if(tmp < 0) return -tmp;
        return tmp;
    }

    int MASK(int j)
    {
        return (1 << j);
    }

    int BIT(int tmp, int j)
    {
        int x = tmp & MASK(j);
        if(x != 0) return 1;
        return 0;
    }
};

void __setup()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
}

int main()
{
    __setup();

    int t = 1;
//    cin >> t;
    for(int i = 1; i <= t; i++)
    {
        Solution().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 340 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 340 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 340 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 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 3 ms 724 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 340 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 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 3 ms 724 KB Output is correct
13 Correct 229 ms 33092 KB Output is correct
14 Correct 210 ms 33060 KB Output is correct
15 Correct 208 ms 33100 KB Output is correct
16 Correct 231 ms 32924 KB Output is correct
17 Correct 223 ms 32940 KB Output is correct
18 Correct 202 ms 33688 KB Output is correct