oj.uz

Submission #831276

# Submission time Handle Problem Language Result Execution time Memory
831276 2023-08-20T03:43:33 Z 12345678 Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 505 ms 36616 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int nx=2e5+5, sx=2, inf=1e9;
int n, q, idx, df[nx], v[nx], l, r, x;

struct segtree
{
    struct mat:array<array<ll, sx>, sx>
    {
        mat() {
            for (int i=0; i<sx; i++) for (int j=0; j<sx; j++) (*this)[i][j]=-inf;
        }
        mat(int idx)
        {
            (*this)[1][1]=-inf; (*this)[0][1]=0;
            if ((df[idx]^df[idx-1])>=0) (*this)[0][0]=abs(df[idx]), (*this)[1][0]=-inf;
            else (*this)[0][0]=0, (*this)[1][0]=abs(df[idx]);
        }
        friend mat operator*(const mat A, const mat B)
        {
            mat res;
            for (int i=0; i<sx; i++) for (int j=0; j<sx; j++) for (int k=0; k<sx; k++) res[i][j]=max(A[i][k]+B[k][j], res[i][j]);
            return res;
        }
    } d[4*nx];
    void build(int l, int r,  int i)
    {
        if (l==r) return void(d[i]=mat(l));
        int md=(l+r)/2;
        build(md+1, r, 2*i+1);
        build(l, md, 2*i);
        d[i]=d[2*i]*d[2*i+1];
    }
    void update(int l, int r, int i, int idx)
    {
        if (idx<l||r<idx) return;
        if (l==r) return void(d[i]=mat(l));
        int md=(l+r)/2;
        update(l, md, 2*i, idx);
        update(md+1, r, 2*i+1, idx);
        d[i]=d[2*i]*d[2*i+1];
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>q;
    for (int i=1; i<=n; i++) cin>>v[i], df[i]=v[i]-v[i-1];
    s.build(2, n, 1);
    while (q--)
    {
        cin>>l>>r>>x;
        df[l]+=x; df[r+1]-=x;
        s.update(2, n, 1, l);
        s.update(2, n, 1, l+1);
        s.update(2, n, 1, r+1);
        s.update(2, n, 1, r+2);
        cout<<max(s.d[1][0][0], s.d[1][1][0])<<'\n';
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 25300 KB Output is correct
2 Correct 9 ms 25384 KB Output is correct
3 Correct 9 ms 25300 KB Output is correct
4 Correct 9 ms 25300 KB Output is correct
5 Correct 9 ms 25300 KB Output is correct
6 Correct 9 ms 25360 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 25300 KB Output is correct
2 Correct 9 ms 25384 KB Output is correct
3 Correct 9 ms 25300 KB Output is correct
4 Correct 9 ms 25300 KB Output is correct
5 Correct 9 ms 25300 KB Output is correct
6 Correct 9 ms 25360 KB Output is correct
7 Correct 13 ms 25456 KB Output is correct
8 Correct 13 ms 25432 KB Output is correct
9 Correct 14 ms 25428 KB Output is correct
10 Correct 14 ms 25516 KB Output is correct
11 Correct 13 ms 25428 KB Output is correct
12 Correct 13 ms 25516 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 25300 KB Output is correct
2 Correct 9 ms 25384 KB Output is correct
3 Correct 9 ms 25300 KB Output is correct
4 Correct 9 ms 25300 KB Output is correct
5 Correct 9 ms 25300 KB Output is correct
6 Correct 9 ms 25360 KB Output is correct
7 Correct 13 ms 25456 KB Output is correct
8 Correct 13 ms 25432 KB Output is correct
9 Correct 14 ms 25428 KB Output is correct
10 Correct 14 ms 25516 KB Output is correct
11 Correct 13 ms 25428 KB Output is correct
12 Correct 13 ms 25516 KB Output is correct
13 Correct 505 ms 35968 KB Output is correct
14 Correct 466 ms 36024 KB Output is correct
15 Correct 462 ms 35980 KB Output is correct
16 Correct 489 ms 36112 KB Output is correct
17 Correct 477 ms 35884 KB Output is correct
18 Correct 487 ms 36616 KB Output is correct