Submission #1013333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013333		andrei_iorgulescu	Sum Zero (RMI20_sumzero)	C++14	61 / 100	206 ms	33108 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];

const int MOD = 12345;

vector<pair<ll,int>> v[MOD + 5];

int ce(ll val)
{
    int ret = n + 1;
    int cn = (val % MOD + MOD) % MOD;
    for (auto it : v[cn])
        if (it.first == val)
            ret = it.second;
    return ret;
}

void set_nxt_sp(ll x,int tr)
{
    v[((x % MOD) + MOD) % MOD].push_back({x,tr});
}

void build()
{
    unde[0][n + 1] = n + 1;
    for (int i = n; i >= 1; i--)
    {
        set_nxt_sp(sp[i],i);
        int x = ce(sp[i - 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