Submission #636484

#	Time	Username	Problem	Language	Result	Execution time	Memory
636484		danikoynov	Sum Zero (RMI20_sumzero)	C++14	61 / 100	82 ms	19200 KiB

sumzero

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int maxn = 4e5 + 10, maxlog = 6, base = 10;

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

    unordered_map < ll, 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] << " ";*/
    if (n > 3e5)
        return;
    cin >> q;
    int l, r, jump, st;
    for (int i = 1; i <= q; i ++)
    {
        cin >> l >> r;
        l = l - 1;
        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 /= base;
        }
        cout << jump << endl;
    }
}
void speed()
{
    ios_base::sync_with_stdio((false));
    cin.tie(NULL);
    cout.tie(NULL);
}
int main()
{
    speed();
    //freopen("input.txt", "r", stdin);
    solve();
    return 0;
}
/**

*/

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