Submission #1263304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263304		shakuu	Sum Zero (RMI20_sumzero)	C++20	0 / 100	3 ms	1344 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);
    for (int &i : vec) cin >> i;

    vector<vector<int>> up(n, vector<int>(lg,-1));
    map<int,int> mp;
    mp[0] = 0;
    int sum = 0;
    int lst = -1;
    for (int i = 0; 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; l--, r--;
        for (int j = lg - 1; j >= 0; --j) {
            if (up[r][j] >= 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: 0 / 22
• Subtask 2: 0 / 39
• Subtask 3: 0 / 39