Submission #366697

#	Time	Username	Problem	Language	Result	Execution time	Memory
366697		faustaadp	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	1411 ms	54404 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int NN = 1e6 + 5;
const int mo = 1e9 + 7;
const ld eps = 1e-9;
ll n, q, a[NN];
ll ST[4 * NN][3][3];
ll MI[4 * NN];
ll MA[4 * NN];
ll LZ[4 * NN];
void init(ll aa, ll bb, ll ee)
{
    if(aa == bb)
    {
        MI[ee] = a[aa];
        MA[ee] = a[aa];
        for(ll i = 0; i < 3; i++)
            for(ll j = 0; j < 3; j++)
            {
                if(i != 2 && j != 2)
                    ST[ee][i][j] = -1e18;
                else
                {
                    ll cst = 0;
                    if(i == 0)cst -= MI[ee];
                    if(j == 0)cst -= MI[ee];
                    if(i == 1)cst += MA[ee];
                    if(j == 1)cst += MA[ee];
                    ST[ee][i][j] = cst; 
                }
            }
    }
    else
    {
        ll ce = (aa + bb) / 2;
        init(aa, ce, ee * 2);
        init(ce + 1, bb, ee * 2 + 1);
        MI[ee] = min(MI[ee * 2], MI[ee * 2 + 1]);
        MA[ee] = max(MA[ee * 2], MA[ee * 2 + 1]);
        for(ll i = 0; i < 3; i++)
            for(ll j = 0; j < 3; j++)
            {
                if(i != 2 && j != 2)
                    ST[ee][i][j] = -1e18;
                else
                {
                    ll cst = 0;
                    if(i == 0)cst -= MI[ee];
                    if(j == 0)cst -= MI[ee];
                    if(i == 1)cst += MA[ee];
                    if(j == 1)cst += MA[ee];
                    ST[ee][i][j] = cst; 
                }
            }
        for(ll i = 0; i < 3; i++)
            for(ll j = 0; j < 3; j++)
            {
                ST[ee][i][j] = max(ST[ee][i][j], ST[ee * 2][i][j]);
                ST[ee][i][j] = max(ST[ee][i][j], ST[ee * 2 + 1][i][j]);
                ST[ee][i][j] = max(ST[ee][i][j], ST[ee * 2][i][0] + ST[ee * 2 + 1][1][j]);
                ST[ee][i][j] = max(ST[ee][i][j], ST[ee * 2][i][1] + ST[ee * 2 + 1][0][j]);
                ST[ee][i][j] = max(ST[ee][i][j], ST[ee * 2][i][2] + ST[ee * 2 + 1][2][j]);
            }
    }
    // for(ll i = 0; i < 3; i++)
        // for(ll j = 0; j < 3; j++)
            // cout << aa << " " << bb << "  " << i << "(---)" << j << "  =  " << ST[ee][i][j] << "\n";
}
void turun(ll aa, ll bb, ll ee)
{
    if(LZ[ee])
    {
        MI[ee] += LZ[ee];
        MA[ee] += LZ[ee];
        for(ll i = 0; i < 3; i++)
            for(ll j = 0; j < 3; j++)
            {
                if(i == 0)ST[ee][i][j] -= LZ[ee];
                if(j == 0)ST[ee][i][j] -= LZ[ee];
                if(i == 1)ST[ee][i][j] += LZ[ee];
                if(j == 1)ST[ee][i][j] += LZ[ee];
            }
        if(aa < bb)
        {
            LZ[ee * 2] += LZ[ee];
            LZ[ee * 2 + 1] += LZ[ee];
        }
        LZ[ee] = 0;
    }
}
void upd(ll aa, ll bb, ll cc, ll dd, ll ee, ll ff)
{
    turun(aa, bb, ee);
    if(bb < cc || dd < aa)
        return ;
    else
    if(cc <= aa && bb <= dd)
    {
        LZ[ee] += ff;
        turun(aa, bb, ee);
    }
    else
    {
        ll ce = (aa + bb) / 2;
        upd(aa, ce, cc, dd, ee * 2, ff);
        upd(ce + 1, bb, cc, dd, ee * 2 + 1, ff);
        MI[ee] = min(MI[ee * 2], MI[ee * 2 + 1]);
        MA[ee] = max(MA[ee * 2], MA[ee * 2 + 1]);
        for(ll i = 0; i < 3; i++)
            for(ll j = 0; j < 3; j++)
            {
                if(i != 2 && j != 2)
                    ST[ee][i][j] = -1e18;
                else
                {
                    ll cst = 0;
                    if(i == 0)cst -= MI[ee];
                    if(j == 0)cst -= MI[ee];
                    if(i == 1)cst += MA[ee];
                    if(j == 1)cst += MA[ee];
                    ST[ee][i][j] = cst; 
                }
            }
        for(ll i = 0; i < 3; i++)
            for(ll j = 0; j < 3; j++)
            {
                ST[ee][i][j] = max(ST[ee][i][j], ST[ee * 2][i][j]);
                ST[ee][i][j] = max(ST[ee][i][j], ST[ee * 2 + 1][i][j]);
                ST[ee][i][j] = max(ST[ee][i][j], ST[ee * 2][i][0] + ST[ee * 2 + 1][1][j]);
                ST[ee][i][j] = max(ST[ee][i][j], ST[ee * 2][i][1] + ST[ee * 2 + 1][0][j]);
                ST[ee][i][j] = max(ST[ee][i][j], ST[ee * 2][i][2] + ST[ee * 2 + 1][2][j]);
            }
    }
}
// ll d[3030][4];
// ll depe(ll pos, ll tr)
// {
//     if(pos > n && tr == 0)
//         return 0;
//     if(pos > n)
//         return -1e18;
//     ll &ret = d[pos][tr];
//     if(ret == -1)
//     {
//         ret = depe(pos + 1, tr);
//         if(tr == 0)
//         {
//             ret = max(ret, depe(pos + 1, 1) + a[pos]);
//             ret = max(ret, depe(pos + 1, 2) - a[pos]);
//         }
//         else
//         if(tr == 1)
//             ret = max(ret, depe(pos + 1, 0) - a[pos]);
//         else
//             ret = max(ret, depe(pos + 1, 0) + a[pos]);
//     } 
//     return ret;
// }
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> q;
    // while(1)
    {   
        for(ll i = 1; i <= n; i++)
        {
            // a[i] = rand() % 10;
            cin >> a[i];
            // cout << a[i] << " ";
        }
        // cout << "\n";
        init(1, n, 1);
        for(ll i = 1; i <= q; i++)
        {
            ll L, R, tam;
            cin >> L >> R >> tam;
            upd(1, n, L, R, 1, tam);
            // for(ll i = L; i <= R; i++)
                // a[i] += tam;
            // init(1, n, 1);
            // memset(d, -1, sizeof(d));
            cout << ST[1][2][2] << "\n";
            // cout << ST[1][2][2] << " " << depe(1, 0) << "\n";
            // if(ST[1][2][2] != depe(1, 0))
            // {
                // return 0;
            // }
        }
    }
}
    

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55