Submission #1263309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263309		shakuu	Sum Zero (RMI20_sumzero)	C++20	22 / 100	92 ms	22596 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using ll = long long;

#define int long long

// #define test_cases

const int MOAI = 1e9 + 7, inf = 1e18;
const int N = 1e6;

const int lg = 18;

void solve()
{
    int n; cin >> n;
    vector<int> vec(n+1);
    for (int i = 1; i <= n; ++i) cin >> vec[i];

    vector<vector<int>> up(n+1, vector<int>(lg,-1));
    map<int,int> mp;
    mp[0] = 0;
    int sum = 0;
    int lst = -1;
    for (int i = 1; i <=  n; ++i) {
        sum += vec[i];
        if (mp.count(sum)) lst = max(lst, mp[sum]);
        up[i][0] = lst;
        for (int j = 1; j < lg; ++j) {
            if (up[i][j-1] != -1)up[i][j] = up[up[i][j-1]][j-1];
        } 
        mp[sum] = i;
    }

    int q; cin >> q;
    while (q--) {
        int l, r, ans = 0; cin >> l >> r;
        for (int j = lg - 1; j >= 0; --j) {
            if (up[r][j] != -1 && up[r][j] + 1 >= l) {
                ans += (1 << j);
                r = up[r][j];
            }
        }
        cout << ans << '\n';
    }  
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);

    int t = 1;
#ifdef test_cases
    cin >> t;
#endif
    while (t--)
    {
        solve();
        cout << '\n';
    }
}

/*
                                                                        
 ▄█▀▀▀█▄█████▀  ▀████▀▀     ██     ▀████▀ ▀███▀▀███▀   ▀███▀███▀   ▀███▀
▄██    ▀█ ██      ██       ▄██▄      ██   ▄█▀   ██       █  ██       █  
▀███▄     ██      ██      ▄█▀██▄     ██ ▄█▀     ██       █  ██       █  
  ▀█████▄ ██████████     ▄█  ▀██     █████▄     ██       █  ██       █  
▄     ▀██ ██      ██     ████████    ██  ███    ██       █  ██       █  
██     ██ ██      ██    █▀      ██   ██   ▀██▄  ██▄     ▄█  ██▄     ▄█  
█▀█████▀▄████▄  ▄████▄▄███▄   ▄████▄████▄   ███▄ ▀██████▀▀   ▀██████▀▀  

*/

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