oj.uz

Submission #366697

# Submission time Handle Problem Language Result Execution time Memory
366697 2021-02-15T04:15:06 Z faustaadp Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 1411 ms 54404 KB 
#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.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 380 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 10 ms 1260 KB Output is correct
8 Correct 10 ms 1260 KB Output is correct
9 Correct 10 ms 1280 KB Output is correct
10 Correct 10 ms 1260 KB Output is correct
11 Correct 10 ms 1260 KB Output is correct
12 Correct 15 ms 1260 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 380 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 10 ms 1260 KB Output is correct
8 Correct 10 ms 1260 KB Output is correct
9 Correct 10 ms 1280 KB Output is correct
10 Correct 10 ms 1260 KB Output is correct
11 Correct 10 ms 1260 KB Output is correct
12 Correct 15 ms 1260 KB Output is correct
13 Correct 1411 ms 53996 KB Output is correct
14 Correct 1382 ms 54380 KB Output is correct
15 Correct 1383 ms 54384 KB Output is correct
16 Correct 1384 ms 54328 KB Output is correct
17 Correct 1386 ms 54252 KB Output is correct
18 Correct 1399 ms 54404 KB Output is correct