Submission #1013321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013321		andrei_iorgulescu	Sum Zero (RMI20_sumzero)	C++14	61 / 100	266 ms	39248 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int n,a[400005],q;
ll sp[400005];
int p4[10];
int unde[10][400005];
map<ll,int> nxt_sp;

void build()
{
    unde[0][n + 1] = n + 1;
    for (int i = n; i >= 1; i--)
    {
        nxt_sp[sp[i]] = i;
        int x = nxt_sp[sp[i - 1]];
        if (x == 0)
            x = n + 1;
        unde[0][i] = min(x,unde[0][i + 1]);
    }
    for (int j = 1; j <= 9; j++)
    {
        unde[j][n + 1] = n + 1;
        for (int i = 1; i <= n; i++)
        {
            int pz = i;
            for (int q = 1; q <= 3; q++)
            {
                pz = unde[j - 1][pz] + 1;
                if (pz > n + 1)
                    pz = n + 1;
            }
            unde[j][i] = unde[j - 1][pz];
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i],sp[i] = sp[i - 1] + a[i];
    p4[0] = 1;
    for (int i = 1; i <= 9; i++)
        p4[i] = 4 * p4[i - 1];
    build();
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        int l,r;
        cin >> l >> r;
        int ans = 0;
        int p = l;
        for (int pas = 9; pas >= 0; pas--)
        {
            while (unde[pas][p] <= r)
            {
                ans += p4[pas];
                p = unde[pas][p] + 1;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

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