Submission #1263310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263310		shakuu	Sum Zero (RMI20_sumzero)	C++20	61 / 100	511 ms	72228 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(lg, vector<int>(n+1,-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[0][i] = lst;
        for (int j = 1; j < lg; ++j) {
            if (up[j-1][i] != -1)up[j][i] = up[j-1][up[j-1][i]];
        } 
        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[j][r] != -1 && up[j][r] + 1 >= l) {
                ans += (1 << j);
                r = up[j][r];
            }
        }
        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: 39 / 39
• Subtask 3: 0 / 39