oj.uz

Submission #1030119

# Submission time Handle Problem Language Result Execution time Memory
1030119 2024-07-21T20:36:49 Z parsadox2 Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 258 ms 38184 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 10;
int n , a[N] , d[N] , q;

struct SEG{
    struct NODE{
        int dp[2][2];
        NODE()
        {
            memset(dp , 0 , sizeof dp);
        }
    };
    NODE t[N << 2];
    NODE Merge(NODE lc , NODE rc , int lim)
    {
        NODE res;
        if((d[lim] < 0 && d[lim - 1] > 0) || (d[lim] > 0 && d[lim - 1] < 0))
        {
            for(int i = 0 ; i < 2 ; i++)  for(int j = 0 ; j < 2 ; j++)
                res.dp[i][j] = max(lc.dp[i][0] + rc.dp[1][j] , lc.dp[i][1] + rc.dp[0][j]);
        }
        else
        {
            for(int i = 0 ; i < 2 ; i++)  for(int j = 0 ; j < 2 ; j++)
                res.dp[i][j] = lc.dp[i][1] + rc.dp[1][j];
        }
        return res;
    }
    void Build(int node = 1 , int nl = 1 , int nr = n)
    {
        if(nr - nl == 1)
        {
            t[node].dp[1][1] = abs(d[nl]);
            return;
        }
        int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
        Build(lc , nl , mid);  Build(rc , mid , nr);
        t[node] = Merge(t[lc] , t[rc] , mid);
    }
    void Update(int id , int node = 1 , int nl = 1 , int nr = n)
    {
        if(nr - nl == 1)
        {
            t[node].dp[1][1] = abs(d[nl]);
            return;
        }
        int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
        if(id < mid)
            Update(id , lc , nl , mid);
        else
            Update(id , rc , mid , nr);
        t[node] = Merge(t[lc] , t[rc] , mid);
    }
} seg;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);  cout.tie(0);
    cin >> n >> q;
    for(int i = 0 ; i < n ; i++)
        cin >> a[i];
    for(int i = 1 ; i < n ; i++)
        d[i] = a[i] - a[i - 1];
    seg.Build();
    for(int i = 0 ; i < q ; i++)
    {
        int l , r , x;  cin >> l >> r >> x;  l--;
        if(l != 0)
        {
            d[l] += x;
            seg.Update(l);
        }
        if(r != n)
        {
            d[r] -= x;
            seg.Update(r);
        }
        cout << seg.t[1].dp[1][1] << '\n';
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 25436 KB Output is correct
2 Correct 8 ms 25436 KB Output is correct
3 Correct 11 ms 25356 KB Output is correct
4 Correct 9 ms 25432 KB Output is correct
5 Correct 9 ms 25436 KB Output is correct
6 Correct 9 ms 25436 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 25436 KB Output is correct
2 Correct 8 ms 25436 KB Output is correct
3 Correct 11 ms 25356 KB Output is correct
4 Correct 9 ms 25432 KB Output is correct
5 Correct 9 ms 25436 KB Output is correct
6 Correct 9 ms 25436 KB Output is correct
7 Correct 11 ms 25692 KB Output is correct
8 Correct 11 ms 25688 KB Output is correct
9 Correct 12 ms 25944 KB Output is correct
10 Correct 12 ms 25688 KB Output is correct
11 Correct 11 ms 25688 KB Output is correct
12 Correct 11 ms 25692 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 25436 KB Output is correct
2 Correct 8 ms 25436 KB Output is correct
3 Correct 11 ms 25356 KB Output is correct
4 Correct 9 ms 25432 KB Output is correct
5 Correct 9 ms 25436 KB Output is correct
6 Correct 9 ms 25436 KB Output is correct
7 Correct 11 ms 25692 KB Output is correct
8 Correct 11 ms 25688 KB Output is correct
9 Correct 12 ms 25944 KB Output is correct
10 Correct 12 ms 25688 KB Output is correct
11 Correct 11 ms 25688 KB Output is correct
12 Correct 11 ms 25692 KB Output is correct
13 Correct 257 ms 37712 KB Output is correct
14 Correct 226 ms 37576 KB Output is correct
15 Correct 258 ms 37824 KB Output is correct
16 Correct 218 ms 37452 KB Output is correct
17 Correct 219 ms 37460 KB Output is correct
18 Correct 223 ms 38184 KB Output is correct