Submission #478434

#	Time	Username	Problem	Language	Result	Execution time	Memory
478434		SlavicG	Sum Zero (RMI20_sumzero)	C++17	61 / 100	159 ms	19532 KiB

sumzero

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

ll a[100005], p[100005];
int nxt[20][100005];
void solve()
{   
    forn(i, 20)forn(j,100005)nxt[i][j] = -1;
    int n, q;
    cin >> n;
    for(int i = 1;i <= n;++i){
        cin >> a[i];
        p[i] = p[i - 1] + a[i];
    }    

    cin >> q;
    map<ll,int> m;

    for(int i = n; i >= 0;--i){
        if(a[i] == 0)nxt[0][i] = i;        
        if(m.count(p[i]))nxt[0][i + 1] = m[p[i]];
        m[p[i]] = i;
    }

    for(int i = n - 1;i >= 1;--i){
        if(nxt[0][i + 1] != -1){
            if(nxt[0][i] == -1)nxt[0][i] = nxt[0][i + 1];
            nxt[0][i] = min(nxt[0][i], nxt[0][i + 1]);
        }
    }

    for(int j = 1;j < 20;++j){
        for(int i = 1;i <= n;++i){
            if(nxt[j - 1][i]  != -1){
                nxt[j][i] = nxt[j - 1][nxt[j - 1][i] + 1];
            }
        }

    }

    while(q--)
    {
        int l, r;
        cin >> l >> r;

        int i = l;
        ll ans = 0;
        for(int j = 19;j >= 0;--j){
            if(nxt[j][i] != -1 && i <= r && nxt[j][i] <= r){
                ans += (1 << j);
                i = nxt[j][i] + 1;
            }
        }
        cout << ans << "\n";
    }
}   
 
int32_t main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--)
    {
        solve();
    }
}

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