Submission #1013343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013343		andrei_iorgulescu	Sum Zero (RMI20_sumzero)	C++14	61 / 100	329 ms	22892 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int n,q;
ll sp[400005];
int p4[10];
int unde[4][400005];

const int MOD = 1e3 + 17;

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

int nxt_sp(ll val)
{
    int huh = val % MOD;
    if (huh < 0)
        huh += MOD;
    for (auto it : v[huh])
        if (it.first == val)
            return it.second;
    return 0;
}

void set_nxt_sp(ll x,int tr)
{
    int huh = x % MOD;
    if (huh < 0)
        huh += MOD;
    for (int i = 0; i < v[huh].size(); i++)
        if (v[huh][i].first == x)
        {
            v[huh][i].second = tr;
            return;
        }
    v[huh].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 = 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 <= 3; j++)
    {
        unde[j][n + 1] = n + 1;
        for (int i = 1; i <= n; i++)
        {
            int pz = i;
            for (int q = 1; q <= 19; 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 >> sp[i],sp[i] += sp[i - 1];
    p4[0] = 1;
    for (int i = 1; i <= 3; i++)
        p4[i] = 20 * 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 = 3; pas >= 0; pas--)
        {
            while (unde[pas][p] <= r)
            {
                ans += p4[pas];
                p = unde[pas][p] + 1;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

Compilation message (stderr)

sumzero.cpp: In function 'void set_nxt_sp(ll, int)':
sumzero.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < v[huh].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~

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