Submission #636477

#	Time	Username	Problem	Language	Result	Execution time	Memory
636477		danikoynov	Sum Zero (RMI20_sumzero)	C++14	0 / 100	11 ms	596 KiB

sumzero

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 4e5 + 10, maxlog = 7, base = 8;

int n, dp[maxn][maxlog], q;
ll a[maxn], pref[maxn];
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        pref[i] = pref[i - 1] + a[i];
    }

    map < int, int > last;
    int cl = n + 1;
    dp[n + 1][0] = n + 1;
    for (int i = n; i >= 0; i --)
    {
        if (last[pref[i]] != 0)
        cl = min(cl, last[pref[i]]);
        dp[i][0] = cl;
        //cout << i << " : " << cl << endl;
        last[pref[i]] = i;
    }

    for (int j = 1; j < maxlog; j ++)
        for (int i = 0; i <= n + 1; i ++)
        {
            dp[i][j] = dp[i][j - 1];
            for (int f = 1; f < base; f ++)
            dp[i][j] = dp[dp[i][j]][j - 1];
        }
    /**for (int j = 0; j < 4; j ++, cout << endl)
        for (int i = 0; i <= n; i ++)
        cout << dp[i][j] << " ";*/

    cin >> q;
    for (int i = 1; i <= q; i ++)
    {
        int l, r;
        cin >> l >> r;
        l = l - 1;
        int jump = 0, st = 1;
        for (int bit = 1; bit < maxlog; bit ++)
            st = st * base;
        for (int bit = maxlog - 1; bit >= 0; bit --)
        {
            //cout << l << " " << jump << endl;
            for (int f = 0; f < base; f ++)
            {
            if (dp[l][bit] <= r)
            {
                //cout << dp[l][bit] << endl;
                jump += st;
                l = dp[l][bit];
            }
            }
        st /= 10;
        }
        cout << jump << endl;
    }
}
int main()
{
    //freopen("input.txt", "r", stdin);
    solve();
   return 0;
}
/**

*/

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