Submission #634986

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

sumzero

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10, maxlog = 19;

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[dp[i][j - 1]][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;
        for (int bit = maxlog - 1; bit >= 0; bit --)
        {
            //cout << l << " " << jump << endl;
            if (dp[l][bit] <= r)
            {
                //cout << dp[l][bit] << endl;
                jump += (1 << bit);
                l = dp[l][bit] + 1;
            }
        }
        cout << jump << endl;
    }
}
int main()
{
    solve();
   return 0;
}

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