Submission #1291383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291383		xorreverse	Sjeckanje (COCI21_sjeckanje)	C++20	110 / 110	1037 ms	136472 KiB

Main

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long
using namespace std;
const int maxN = 2e5 + 5;
int n, q, a[maxN];
struct node{
    int D[4][4];
    int G[4];
    // chi can quan tam la co max va min chua
    int lz = 0;
};
node st[4 * maxN];
bool testBit(int x, int k){
    return x & (1 << k);
}
void build(int x, int l, int r){
    if (l > r) return;
    if (l == r){
        memset(st[x].D, -0x3f, sizeof(st[x].D));
        memset(st[x].G, -0x3f, sizeof(st[x].G));
        st[x].G[0] = 0;
        st[x].G[1] = a[l];
        st[x].G[2] = -a[l];
        st[x].G[3] = 0;
        return;
    }
    int mid = (l + r) / 2;
    build(x * 2, l, mid);
    build(x * 2 + 1, mid + 1, r);
    memset(st[x].D, -0x3f, sizeof(st[x].D));
    memset(st[x].G, -0x3f, sizeof(st[x].G));
    for (int j = 0; j < 4; j ++){
        for (int k = 0; k < 4; k ++){

                    st[x].D[j][k] = max(st[x].D[j][k], st[x * 2].D[j][0] + st[x * 2 + 1].D[3][k]);

                    st[x].D[j][k] = max(st[x].D[j][k], st[x * 2].D[j][1] + st[x * 2 + 1].D[2][k]);

                    st[x].D[j][k] = max(st[x].D[j][k], st[x * 2].D[j][2] + st[x * 2 + 1].D[1][k]);

                    st[x].D[j][k] = max(st[x].D[j][k], st[x * 2].D[j][3] + st[x * 2 + 1].D[0][k]);
                    st[x].D[j][k] = max(st[x].D[j][k], st[x * 2].D[j][3] + st[x * 2 + 1].D[3][k]);

        }
    }

    for (int k = 0; k < 4; k ++){

            for (int u = 0; u < 4; u ++){

                    st[x].D[u][k] = max(st[x].D[u][k], st[x * 2].G[u] + st[x * 2 + 1].D[3][k]);
            }
    }

    for (int j = 0; j < 4; j ++){

            for (int v = 0; v < 4; v ++){

                    st[x].D[j][v] = max(st[x].D[j][v], st[x * 2].D[j][3] + st[x *2  +1].G[v]);
            }
    }

        for (int k = 0; k < 4; k ++){
            for (int u = 0; u < 4; u ++){
                for (int v = 0; v < 4; v ++){
                    if ((u & v) == 0) st[x].D[u | v][k] = max(st[x].D[u | v][k], st[x * 2].G[u] + st[x * 2 + 1].D[v][k]);
                }
            }
        }
    for (int j = 0; j < 4; j ++){
        for (int u = 0; u < 4; u ++){
                for (int v = 0; v < 4; v ++){
                    if ((u & v) == 0) st[x].D[j][u | v] = max(st[x].D[j][u | v], st[x * 2].D[j][u] + st[x * 2 + 1].G[v]);
                }
            }
    }
    for (int j = 0; j < 4; j ++){
        for (int k = 0; k < 4; k ++){
            st[x].D[j][k] = max(st[x].D[j][k], st[x * 2].G[j] + st[x * 2 + 1].G[k]);
        }
    }
        for (int k = 0; k < 4; k ++){
            for (int u = 0; u < 4; u ++){
                if (testBit(k, 0) && testBit(u, 0)) continue;
                if (testBit(k, 1) && testBit(u, 1)) continue;
                st[x].G[u| k] = max(st[x].G[u | k], st[x * 2].G[u] + st[x * 2 + 1].G[k]);
            }
        }

    //cout << x << " " << l << " " << r << " " << st[x].D[3][3] << " " << st[x].G[2] << " " << st[x].G[1]<< '\n';
    st[x].lz = 0;
}
void lazy(int x){
    st[x * 2].lz += st[x].lz;
    int chg = st[x].lz;
    st[x * 2 + 1].lz += st[x].lz;
        for (int j = 0; j < 4; j ++){
            if (testBit(j, 0)) st[x * 2].G[j] += chg;
            if (testBit(j, 1)) st[x * 2].G[j] -= chg;
        }
        for (int j = 0; j <4 ; j ++){
            for (int k = 0; k < 4;k ++){
                if (testBit(j, 0)) st[x * 2].D[j][k] += chg;
                if (testBit(j, 1)) st[x * 2].D[j][k] -= chg;
                if (testBit(k, 0)) st[x * 2].D[j][k] += chg;
                if (testBit(k, 1)) st[x * 2].D[j][k] -= chg;
            }
        }

        for (int j = 0; j < 4; j ++){
            if (testBit(j, 0)) st[x * 2 + 1].G[j] += chg;
            if (testBit(j, 1)) st[x * 2 + 1].G[j] -= chg;
        }
        for (int j = 0; j <4 ; j ++){
            for (int k = 0; k < 4;k ++){
                if (testBit(j, 0)) st[x * 2 + 1].D[j][k] += chg;
                if (testBit(j, 1)) st[x * 2 + 1].D[j][k] -= chg;
                if (testBit(k, 0)) st[x * 2 + 1].D[j][k] += chg;
                if (testBit(k, 1)) st[x * 2 + 1].D[j][k] -= chg;
            }
        }
    st[x].lz = 0;
}
void up(int x, int l, int r, int u, int v, int chg){
    if (l > r || l > v || r < u) return;
    if (l >= u && r <= v){
        for (int j = 0; j < 4; j ++){
            if (testBit(j, 0)) st[x].G[j] += chg;
            if (testBit(j, 1)) st[x].G[j] -= chg;
        }
        for (int j = 0; j <4 ; j ++){
            for (int k = 0; k < 4;k ++){
                if (testBit(j, 0)) st[x].D[j][k] += chg;
                if (testBit(j, 1)) st[x].D[j][k] -= chg;
                if (testBit(k, 0)) st[x].D[j][k] += chg;
                if (testBit(k, 1)) st[x].D[j][k] -= chg;
            }
        }
        st[x].lz += chg;
        return;
    }
    lazy(x);
    int mid = (l + r) / 2;
    up(x * 2, l, mid, u, v, chg);
    up(x * 2 + 1, mid + 1, r, u, v, chg);
    memset(st[x].D, -0x3f, sizeof(st[x].D));
    memset(st[x].G, -0x3f, sizeof(st[x].G));
    for (int j = 0; j < 4; j ++){
        for (int k = 0; k < 4; k ++){

                    st[x].D[j][k] = max(st[x].D[j][k], st[x * 2].D[j][0] + st[x * 2 + 1].D[3][k]);

                    st[x].D[j][k] = max(st[x].D[j][k], st[x * 2].D[j][1] + st[x * 2 + 1].D[2][k]);

                    st[x].D[j][k] = max(st[x].D[j][k], st[x * 2].D[j][2] + st[x * 2 + 1].D[1][k]);

                    st[x].D[j][k] = max(st[x].D[j][k], st[x * 2].D[j][3] + st[x * 2 + 1].D[0][k]);
                    st[x].D[j][k] = max(st[x].D[j][k], st[x * 2].D[j][3] + st[x * 2 + 1].D[3][k]);

        }
    }

    for (int k = 0; k < 4; k ++){

            for (int u = 0; u < 4; u ++){

                    st[x].D[u][k] = max(st[x].D[u][k], st[x * 2].G[u] + st[x * 2 + 1].D[3][k]);
            }
    }

    for (int j = 0; j < 4; j ++){

            for (int v = 0; v < 4; v ++){

                    st[x].D[j][v] = max(st[x].D[j][v], st[x * 2].D[j][3] + st[x *2  +1].G[v]);
            }
    }

        for (int k = 0; k < 4; k ++){
            for (int u = 0; u < 4; u ++){
                for (int v = 0; v < 4; v ++){
                    if ((u & v) == 0) st[x].D[u | v][k] = max(st[x].D[u | v][k], st[x * 2].G[u] + st[x * 2 + 1].D[v][k]);
                }
            }
        }
    for (int j = 0; j < 4; j ++){
        for (int u = 0; u < 4; u ++){
                for (int v = 0; v < 4; v ++){
                    if ((u & v) == 0) st[x].D[j][u | v] = max(st[x].D[j][u | v], st[x * 2].D[j][u] + st[x * 2 + 1].G[v]);
                }
            }
    }
    for (int j = 0; j < 4; j ++){
        for (int k = 0; k < 4; k ++){
            st[x].D[j][k] = max(st[x].D[j][k], st[x * 2].G[j] + st[x * 2 + 1].G[k]);
        }
    }

        for (int k = 0; k < 4; k ++){
            for (int u = 0; u < 4; u ++){
                if (testBit(k, 0) && testBit(u, 0)) continue;
                if (testBit(k, 1) && testBit(u, 1)) continue;
                st[x].G[u| k] = max(st[x].G[u | k], st[x * 2].G[u] + st[x * 2 + 1].G[k]);
            }
        }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    build(1, 1, n);
  //  cout << max(st[1].G[3], st[1].D[3][3]) << '\n';
    while (q --){
        int l, r, x; cin >> l >> r >> x;
        up(1, 1, n, l, r, x);

    cout << max(st[1].G[3], st[1].D[3][3]) << '\n';
       // cout << max(st[1].D[0][0][0], st[1].D[1][0][0]) << '\n';
    }
}

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