oj.uz

Submission #367568

# Submission time Handle Problem Language Result Execution time Memory
367568 2021-02-17T16:59:42 Z MrRobot_28 Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 538 ms 23020 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 100;
int tree[4 * N][2][2];
int d[N];
void build(int v, int l, int r)
{
    if(l == r)
    {
        tree[v][0][0] = 0;
        tree[v][1][1] = abs(d[l]);
        return;
    }
    int m = (r + l) / 2;
    build(v * 2, l, m);
    build(v * 2 + 1, m + 1, r);
    for(int i = 0; i < 2; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            tree[v][i][j] = 0;
            for(int t = 0; t < 2; t++)
            {
                int t1 = t ^ (d[m] * d[m + 1] < 0);
                tree[v][i][j] = max(tree[v][i][j], tree[v * 2][i][t] + tree[v * 2 + 1][t1][j]);
            }
        }
    }
}
void update(int v, int l, int r, int ind)
{
    if(l == r)
    {
        tree[v][0][0] = 0;
        tree[v][1][1] = abs(d[l]);
        return;
    }
    int m = (r + l) / 2;
    if(ind <= m)
    {
        update(v * 2, l, m, ind);
    }
    if(ind > m)
    {
        update(v * 2 + 1, m + 1, r, ind);
    }
    for(int i = 0; i < 2; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            tree[v][i][j] = 0;
            for(int t = 0; t < 2; t++)
            {
                int t1 = t ^ (d[m] * d[m + 1] < 0);
                tree[v][i][j] = max(tree[v][i][j], tree[v * 2][i][t] + tree[v * 2 + 1][t1][j]);
            }
        }
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    vector <int> a(n);
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for(int i = 0; i < n - 1; i++)
    {
        d[i] = a[i + 1] - a[i];
    }
    build(1, 0, n - 1);
    while(q--)
    {
        int l, r, x;
        cin >> l >> r >> x ;
        l--;
        r--;
        if(l != 0)
        {
            d[l - 1] += x;
            update(1, 0, n - 1, l - 1);
        }
        if(r != n - 1)
        {
            d[r] -= x;
            update(1, 0, n - 1, r);
        }
        int ans = 0;
        for(int i = 0; i < 2; i++)
        {
            for(int j = 0; j < 2; j++)
            {
                ans = max(ans, tree[1][i][j]);
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 4 ms 748 KB Output is correct
8 Correct 4 ms 748 KB Output is correct
9 Correct 4 ms 748 KB Output is correct
10 Correct 4 ms 748 KB Output is correct
11 Correct 13 ms 748 KB Output is correct
12 Correct 13 ms 748 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 4 ms 748 KB Output is correct
8 Correct 4 ms 748 KB Output is correct
9 Correct 4 ms 748 KB Output is correct
10 Correct 4 ms 748 KB Output is correct
11 Correct 13 ms 748 KB Output is correct
12 Correct 13 ms 748 KB Output is correct
13 Correct 507 ms 22804 KB Output is correct
14 Correct 456 ms 22936 KB Output is correct
15 Correct 463 ms 22764 KB Output is correct
16 Correct 538 ms 22884 KB Output is correct
17 Correct 479 ms 22764 KB Output is correct
18 Correct 439 ms 23020 KB Output is correct