oj.uz

Submission #1011651

# Submission time Handle Problem Language Result Execution time Memory
1011651 2024-07-01T03:02:34 Z Yang8on Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 212 ms 23380 KB 
#include <bits/stdc++.h>
#define Y8o "Sjeckanje"
#define maxn (int) 2e5 + 5
#define ll long long
#define pii pair<int, int>
#define gb(i, j) ((i >> j) & 1)
//#define f first
//#define s second

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
    return uniform_int_distribution<ll> (l, r) (rng);
}
void iof() {
    if(fopen(Y8o".inp", "r"))
    {
        freopen(Y8o".inp", "r", stdin);
//        freopen(Y8o".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(NULL), cout.tie(NULL);
}
void ctime() {
    cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}


int n, Q;
ll a[maxn], d[maxn];

struct dl {
    ll op_op, op_cl, cl_op, cl_cl;
    void cb(dl x, dl y, int mid)
    {
        op_op = max(x.op_op + y.cl_op, x.op_cl + y.op_op);
        op_cl = max(x.op_op + y.cl_cl, x.op_cl + y.op_cl);
        cl_op = max(x.cl_op + y.cl_op, x.cl_cl + y.op_op);
        cl_cl = max(x.cl_op + y.cl_cl, x.cl_cl + y.op_cl);

        if((d[mid] <= 0 && d[mid + 1] <= 0) || (d[mid] >= 0 & d[mid + 1] >= 0))
        {
            op_op = max(x.op_op, x.op_cl) + max(y.op_op, y.cl_op);
            op_cl = max(x.op_op, x.op_cl) + max(y.op_cl, y.cl_cl);
            cl_op = max(x.cl_op, x.cl_cl) + max(y.cl_op, y.op_op);
            cl_cl = max(x.cl_op, x.cl_cl) + max(y.op_cl, y.cl_cl);
        }
    }
} st[4 * maxn];

dl change(ll val, dl best = {0, 0, 0, 0}) {
        best = {val, 0, 0, 0};
        return best;
}
//dl cb(dl x, dl y, int mid, dl best = {0, 0, 0, 0}) {
//        best.op_op = max(x.op_op + y.cl_op, x.op_cl + y.op_op);
//        best.op_cl = max(x.op_op + y.cl_cl, x.op_cl + y.op_cl);
//        best.cl_op = max(x.cl_op + y.cl_op, x.cl_cl + y.op_op);
//        best.cl_cl = max(x.cl_op + y.cl_cl, x.cl_cl + y.op_cl);
//
//        if((d[mid - 1] < 0 && d[mid] < 0) || (d[mid - 1] > 0 && d[mid] > 0))
//        {
//            best.op_op = max(x.op_cl, x.op_op) + max(y.op_op, y.cl_op);
//            best.op_cl = max(x.op_cl, x.op_op) + max(y.op_cl, y.cl_cl);
//            best.cl_op = max(x.cl_op, x.cl_cl) + max(y.op_op, y.cl_op);
//            best.cl_cl = max(x.cl_op, x.cl_cl) + max(y.op_cl, y.cl_cl);
//        }
//        return best;
//}

void build(int id = 1, int l = 1, int r = n - 1)
{
    if(l == r) { st[id] = change(abs(d[l])); return; }
    int mid = (l + r) >> 1;
    build(id * 2, l, mid), build(id * 2 + 1, mid + 1, r);
    st[id].cb(st[id * 2], st[id * 2 + 1], mid);
}
void update(int i, int id = 1, int l = 1, int r = n - 1)
{
    if(i < l || r < i) return ;
    if(l == r) { st[id] = change(abs(d[l])); return; }
    int mid = (l + r) >> 1;
    update(i, id * 2, l, mid), update(i, id * 2 + 1, mid + 1, r);
    st[id].cb(st[id * 2], st[id * 2 + 1], mid);
}

ll ans() {
    return max({ st[1].op_op, st[1].op_cl, st[1].cl_op, st[1].cl_cl });
}

void solve()
{
    cin >> n >> Q;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i < n; i ++) d[i] = a[i] - a[i + 1];

    build();
    for(int i = 1; i <= Q; i ++)
    {
        int u, v; ll val;
        cin >> u >> v >> val;
        d[u - 1] -= val, d[v] += val;
        update(u - 1), update(v);
        cout << ans() << '\n';
    }
}


int main()
{
    iof();

    int nTest = 1;
//    cin >> nTest;

    while(nTest --) {
        solve();
    }

    ctime();
    return 0;
}

Compilation message

Main.cpp: In member function 'void dl::cb(dl, dl, int)':
Main.cpp:42:56: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   42 |         if((d[mid] <= 0 && d[mid + 1] <= 0) || (d[mid] >= 0 & d[mid + 1] >= 0))
      |                                                 ~~~~~~~^~~~
Main.cpp: In function 'void iof()':
Main.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen(Y8o".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 3 ms 4696 KB Output is correct
8 Correct 3 ms 4696 KB Output is correct
9 Correct 5 ms 4700 KB Output is correct
10 Correct 3 ms 4696 KB Output is correct
11 Correct 3 ms 4700 KB Output is correct
12 Correct 2 ms 4700 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 3 ms 4696 KB Output is correct
8 Correct 3 ms 4696 KB Output is correct
9 Correct 5 ms 4700 KB Output is correct
10 Correct 3 ms 4696 KB Output is correct
11 Correct 3 ms 4700 KB Output is correct
12 Correct 2 ms 4700 KB Output is correct
13 Correct 192 ms 23024 KB Output is correct
14 Correct 182 ms 23120 KB Output is correct
15 Correct 191 ms 23124 KB Output is correct
16 Correct 212 ms 23124 KB Output is correct
17 Correct 194 ms 23220 KB Output is correct
18 Correct 168 ms 23380 KB Output is correct