Submission #1283912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283912		canhnam357	Sum Zero (RMI20_sumzero)	C++20	100 / 100	339 ms	21348 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define N 400000
#define LG 12
long long st[N][LG / 3];
pair<long long, int> a[N + 1];
const int mask = (1 << 20) - 1;
int f, g, k, val;
// st[f][g][k] = val;
void change() {
    if (k == 2) {
        st[f][g] = st[f][g] - (st[f][g] & mask) + val;
    }
    else if (k == 1) {
        st[f][g] = ((st[f][g] >> 40) << 40) + val * (1ll << 20) + (st[f][g] & mask);
    }
    else {
        st[f][g] = (st[f][g] & mask) + (1ll << 20) * ((st[f][g] >> 20) & mask) + (1ll << 40) * val;
    }
}
int get() {
    if (k == 2) return (st[f][g] & mask);
    if (k == 1) return ((st[f][g] >> 20) & mask);
    return ((st[f][g] >> 40) & mask);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < LG / 3; j++) {
            st[i][j] = n * (1ll << 40) + n * (1ll << 20) + n;
        }
    }
    long long sum = 0;
    a[0] = {0, -1};
    int x;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        sum += x;
        a[i] = {sum, i - 1};
    }
    sort(a, a + n + 1);
    for (int i = 1; i <= n; i++) {
        if (a[i].first == a[i - 1].first) {
            f = a[i - 1].second + 1;
            g = 0;
            k = 0;
            val = a[i].second;
            change();
        }
    }
    for (int i = n - 2; i >= 0; i--) {
        f = i;
        g = 0;
        k = 2;
        val = (st[i + 1][0] & mask);
        if (val < get()) change();
        k = 1;
        val = ((st[i + 1][0] >> 20) & mask);
        if (val < get()) change();
        k = 0;
        val = ((st[i + 1][0] >> 40) & mask);
        if (val < get()) change();
    }
    int z;
    for (int j = 1; j < LG; j++) {
        for (int i = 0; i + (1 << j) <= n; i++) {
            f = i;
            g = (j - 1) / 3;
            k = (j - 1) % 3;
            z = get();
            if (z + 1 < n) {
                f = z + 1;
                z = get();
                f = i;
                g = j / 3;
                k = j % 3;
                val = z;
                change();
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            f = i;
            g = j / 3;
            k = 2;
            val = (st[i + 1][j / 3] & mask);
            if (val < get()) change();
            k = 1;
            val = ((st[i + 1][j / 3] >> 20) & mask);
            if (val < get()) change();
            k = 0;
            val = ((st[i + 1][j / 3] >> 40) & mask);
            if (val < get()) change();
        }
    }
    int q, l, r, ans;
    cin >> q;
    while (q--) {
        cin >> l >> r;
        l--, r--;
        ans = 0;
        for (int i = LG - 1; i >= 0; i--) {
            while (l <= r) {
                f = l;
                g = i / 3;
                k = i % 3;
                z = get();
                if (z > r) break;
                ans += (1 << i);
                l = z + 1;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 39 / 39
• Subtask 3: 39 / 39