oj.uz

Submission #366696

# Submission time Handle Problem Language Result Execution time Memory
366696 2021-02-15T04:09:18 Z faustaadp Sjeckanje (COCI21_sjeckanje) C++17
55 / 110
 2000 ms 47084 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];
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";
}
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;
            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 5 ms 364 KB Output is correct
2 Correct 4 ms 364 KB Output is correct
3 Correct 4 ms 364 KB Output is correct
4 Correct 5 ms 364 KB Output is correct
5 Correct 5 ms 364 KB Output is correct
6 Correct 5 ms 364 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 364 KB Output is correct
2 Correct 4 ms 364 KB Output is correct
3 Correct 4 ms 364 KB Output is correct
4 Correct 5 ms 364 KB Output is correct
5 Correct 5 ms 364 KB Output is correct
6 Correct 5 ms 364 KB Output is correct
7 Correct 879 ms 1388 KB Output is correct
8 Correct 869 ms 1260 KB Output is correct
9 Correct 903 ms 1412 KB Output is correct
10 Correct 874 ms 1132 KB Output is correct
11 Correct 916 ms 1260 KB Output is correct
12 Correct 855 ms 1408 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 364 KB Output is correct
2 Correct 4 ms 364 KB Output is correct
3 Correct 4 ms 364 KB Output is correct
4 Correct 5 ms 364 KB Output is correct
5 Correct 5 ms 364 KB Output is correct
6 Correct 5 ms 364 KB Output is correct
7 Correct 879 ms 1388 KB Output is correct
8 Correct 869 ms 1260 KB Output is correct
9 Correct 903 ms 1412 KB Output is correct
10 Correct 874 ms 1132 KB Output is correct
11 Correct 916 ms 1260 KB Output is correct
12 Correct 855 ms 1408 KB Output is correct
13 Execution timed out 2087 ms 47084 KB Time limit exceeded
14 Halted 0 ms 0 KB -