Submission #406008

#	Time	Username	Problem	Language	Result	Execution time	Memory
406008		tranxuanbach	Sum Zero (RMI20_sumzero)	C++17	61 / 100	719 ms	53208 KiB

sumzero

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (int i = l; i < r; i++)
#define ForE(i, l, r) for (int i = l; i <= r; i++)
#define FordE(i, l, r) for (int i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <pii> vpii;
typedef vector <vi> vvi;

const int N = 4e5 + 5, M = 19;

int n, q;
int a[N];

ll suf[N]; map <ll, int> mppsuf; int nxt[M][N];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("sumzero.inp", "r", stdin);
    // freopen("sumzero.out", "w", stdout);
    cin >> n;
    ForE(i, 1, n){
        cin >> a[i];
    }
    suf[n + 1] = 0;
    mppsuf[0] = n + 1;
    nxt[0][n + 1] = n + 1;
    FordE(i, n, 1){
        suf[i] = suf[i + 1] + a[i];
        nxt[0][i] = nxt[0][i + 1];
        if (mppsuf.count(suf[i])){
            nxt[0][i] = min(nxt[0][i], mppsuf[suf[i]] - 1);
        }
        mppsuf[suf[i]] = i;
    }
    For(j, 1, M){
        ForE(i, 1, n + 1){
            nxt[j][i] = (nxt[j - 1][i] == n + 1 ? n + 1 : nxt[j - 1][nxt[j - 1][i] + 1]);
        }
    }
    cin >> q; while (q--){
        int l, r; cin >> l >> r;
        int ans = 0;
        FordE(j, M - 1, 0){
            if (l <= r and nxt[j][l] <= r){
                ans += (1 << j);
                l = nxt[j][l] + 1;
            }
        }
        cout << ans << endl;
    }
}

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

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