oj.uz

Submission #404013

# Submission time Handle Problem Language Result Execution time Memory
404013 2021-05-13T16:58:05 Z ScarletS Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 893 ms 51148 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int mn = 2e5+4;
const ll INF = -1e17;
ll seg[mn*4][9],lazy[mn*4];

ll f(int i, int j)
{
    if (j==0||j==6||j==7)
        return seg[i][j];
    if (j==2||j==4)
        return seg[i][j]+lazy[i];
    if (j==1||j==3)
        return seg[i][j]-lazy[i];
    if (j==8)
        return seg[i][j]+lazy[i]*2;
    return seg[i][j]-lazy[i]*2;
}

void passDown(int i)
{
    lazy[i*2+1]+=lazy[i];
    lazy[i*2+2]+=lazy[i];
    lazy[i]=0;
}

void recalc(int i)
{
    int l=(i<<1)+1,r=(i<<1)+2;
    seg[i][0]=max({f(l,0)+f(r,0),f(l,1)+f(r,4),f(l,2)+f(r,3)});
    seg[i][1]=max({f(l,1),f(r,1),f(l,0)+f(r,1),f(l,1)+f(r,7),f(l,2)+f(r,5)});
    seg[i][2]=max({f(l,2),f(r,2),f(l,0)+f(r,2),f(l,1)+f(r,8),f(l,2)+f(r,6)});
    seg[i][3]=max({f(l,3),f(r,3),f(l,3)+f(r,0),f(l,5)+f(r,4),f(l,6)+f(r,3)});
    seg[i][4]=max({f(l,4),f(r,4),f(l,4)+f(r,0),f(l,7)+f(r,4),f(l,8)+f(r,3)});
    seg[i][5]=max({f(l,5),f(r,5),f(l,3)+f(r,1),f(l,5)+f(r,7),f(l,6)+f(r,5)});
    seg[i][6]=max({f(l,6),f(r,6),f(l,3)+f(r,2),f(l,5)+f(r,8),f(l,6)+f(r,6)});
    seg[i][7]=max({f(l,7),f(r,7),f(l,4)+f(r,1),f(l,7)+f(r,7),f(l,8)+f(r,5)});
    seg[i][8]=max({f(l,8),f(r,8),f(l,4)+f(r,2),f(l,7)+f(r,8),f(l,8)+f(r,6)});
}

/**
0: |
1: |-  -1
2: |+  1
3: -|  -1
4: +|  1
5: -|- -2
6: -|+ 0
7: +|- 0
8: +|+ 2
**/

void build(int i, int l, int r)
{
    if (l==r)
    {
        cin>>seg[i][2];
        seg[i][1]=seg[i][3]=-seg[i][2];
        seg[i][4]=seg[i][2];
        for (int j=5;j<9;++j)
            seg[i][j]=INF;
        return;
    }
    build((i<<1)+1,l,(l+r)>>1);
    build((i<<1)+2,((l+r)>>1)+1,r);
    recalc(i);
}

void update(int i, int cL, int cR, int l, int r, int x)
{
    if (r<cL||cR<l)
        return;
    if (l<=cL&&cR<=r)
    {
        lazy[i]+=x;
        return;
    }
    passDown(i);
    update((i<<1)+1,cL,(cL+cR)>>1,l,r,x);
    update((i<<1)+2,((cL+cR)>>1)+1,cR,l,r,x);
    recalc(i);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,q,l,r,x;
    cin>>n>>q;
    build(0,1,n);
    while (q--)
    {
        cin>>l>>r>>x;
        update(0,1,n,l,r,x);
        cout<<seg[0][0]<<"\n";
    }
    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 380 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 9 ms 1108 KB Output is correct
8 Correct 8 ms 1096 KB Output is correct
9 Correct 8 ms 1100 KB Output is correct
10 Correct 7 ms 1100 KB Output is correct
11 Correct 10 ms 1088 KB Output is correct
12 Correct 8 ms 1104 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 380 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 9 ms 1108 KB Output is correct
8 Correct 8 ms 1096 KB Output is correct
9 Correct 8 ms 1100 KB Output is correct
10 Correct 7 ms 1100 KB Output is correct
11 Correct 10 ms 1088 KB Output is correct
12 Correct 8 ms 1104 KB Output is correct
13 Correct 829 ms 50456 KB Output is correct
14 Correct 893 ms 50512 KB Output is correct
15 Correct 845 ms 50464 KB Output is correct
16 Correct 829 ms 50344 KB Output is correct
17 Correct 833 ms 50368 KB Output is correct
18 Correct 815 ms 51148 KB Output is correct