oj.uz

Submission #827262

# Submission time Handle Problem Language Result Execution time Memory
827262 2023-08-16T10:20:29 Z borisAngelov Sjeckanje (COCI21_sjeckanje) C++17
55 / 110
 2000 ms 7980 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 200005;

int n, q;
int a[maxn];

long long dp[maxn];
long long pref[maxn];
long long delta[maxn];

bool is_diff(long long x, long long y)
{
    if (x > 0 && y < 0)
    {
        return true;
    }

    if (x < 0 && y > 0)
    {
        return true;
    }

    return false;
}

void solve()
{
    for (int i = 1; i <= n - 1; ++i)
    {
        delta[i] = a[i + 1] - a[i];
    }

    dp[1] = abs(delta[1]);

    for (int i = 2; i <= n - 1; ++i)
    {
        pref[i] = max(dp[i - 1], pref[i - 1]);

        if (is_diff(delta[i], delta[i - 1]) == false)
        {
            dp[i] = max(dp[i - 1], pref[i - 1]) + abs(delta[i]);
        }
        else
        {
            dp[i] = pref[i - 1] + abs(delta[i]);
        }
    }

    cout << max(dp[n - 1], pref[n - 1]) << "\n";
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> q;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }

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

        for (int j = l; j <= r; ++j)
        {
            a[j] += x;
        }

        solve();
    }

    return 0;
}

/*
4 3
1 2 3 4
1 2 1
1 1 2
2 3 1

4 1
1 2 3 4
1 2 1
*/

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 332 KB Output is correct
3 Correct 1 ms 332 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 332 KB Output is correct
3 Correct 1 ms 332 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 38 ms 532 KB Output is correct
8 Correct 40 ms 588 KB Output is correct
9 Correct 38 ms 468 KB Output is correct
10 Correct 38 ms 468 KB Output is correct
11 Correct 39 ms 524 KB Output is correct
12 Correct 37 ms 532 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 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 38 ms 532 KB Output is correct
8 Correct 40 ms 588 KB Output is correct
9 Correct 38 ms 468 KB Output is correct
10 Correct 38 ms 468 KB Output is correct
11 Correct 39 ms 524 KB Output is correct
12 Correct 37 ms 532 KB Output is correct
13 Execution timed out 2050 ms 7980 KB Time limit exceeded
14 Halted 0 ms 0 KB -