oj.uz

Submission #758290

# Submission time Handle Problem Language Result Execution time Memory
758290 2023-06-14T12:05:20 Z teokakabadze Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 826 ms 29604 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define int long long
#define N 500002
#define M 1000000007
#define pii pair<int, int>
#define piii pair<pii, int>
using namespace std;

int n, t[4 * N][2][2], d[N], a[N], q;

void build(int v, int l, int r)
{
    int i, j, k, p;
    if(l == r) { t[v][1][1] = abs(d[l]); return; }
    int m = (l + r) / 2;
    build(v * 2, l, m);
    build(v * 2 + 1, m + 1, r);
    for(i = 0; i < 2; i++)
    for(j = 0; j < 2; j++)
    for(k = 0; k < 2; k++)
    for(p = 0; p < 2; p++)
    {
        if(k && p && d[m] * d[m + 1] < 0) continue;
        t[v][i][j] = max(t[v][i][j], t[v * 2][i][k] + t[v * 2 + 1][p][j]);
    }
     //cout << l << ' ' << r << ' ' << t[v][0][0] << ' ' << t[v][0][1] << ' ' << t[v][1][0] << ' ' << t[v][1][1] << '\n';
}

void update(int v, int l, int r, int ind, int val)
{
    int i, j, k, p;
    if(l == r) { t[v][1][1] = abs(val); return; }
    int m = (l + r) / 2;
    if(ind <= m) update(v * 2, l, m, ind, val);
    else update(v * 2 + 1, m + 1, r, ind, val);
    for(i = 0; i < 2; i++)
    for(j = 0; j < 2; j++)
    {
        t[v][i][j] = 0;
        for(k = 0; k < 2; k++)
        for(p = 0; p < 2; p++)
        {
            if(k && p && d[m] * d[m + 1] < 0) continue;
            t[v][i][j] = max(t[v][i][j], t[v * 2][i][k] + t[v * 2 + 1][p][j]);
        }
    }
   // cout << l << ' ' << r << ' ' << t[v][0][0] << ' ' << t[v][0][1] << ' ' << t[v][1][0] << ' ' << t[v][1][1] << '\n';
}

main()
{
    std::ios::sync_with_stdio(0);
    cin.tie();
    
    int l, r, x, i;
    cin >> n >> q;
    for(i = 1; i <= n; i++)
    {
        cin >> a[i];
        d[i] = a[i] - a[i - 1];
    }
    build(1, 2, n);
    while(q--)
    {
        cin >> l >> r >> x;
        d[l] += x, d[r + 1] -= x;
        if(l != 1) update(1, 2, n, l, d[l]);
        if(r != n) update(1, 2, n, r + 1, d[r + 1]);
        cout << max(t[1][0][0], max(t[1][0][1], max(t[1][1][0], t[1][1][1]))) << '\n';
    }
}

Compilation message

Main.cpp:53:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   53 | main()
      | ^~~~

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 8 ms 596 KB Output is correct
8 Correct 8 ms 596 KB Output is correct
9 Correct 9 ms 596 KB Output is correct
10 Correct 9 ms 596 KB Output is correct
11 Correct 10 ms 596 KB Output is correct
12 Correct 8 ms 596 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 8 ms 596 KB Output is correct
8 Correct 8 ms 596 KB Output is correct
9 Correct 9 ms 596 KB Output is correct
10 Correct 9 ms 596 KB Output is correct
11 Correct 10 ms 596 KB Output is correct
12 Correct 8 ms 596 KB Output is correct
13 Correct 795 ms 26840 KB Output is correct
14 Correct 826 ms 28988 KB Output is correct
15 Correct 797 ms 29016 KB Output is correct
16 Correct 798 ms 29168 KB Output is correct
17 Correct 796 ms 28904 KB Output is correct
18 Correct 759 ms 29604 KB Output is correct