Submission #646645

#	Time	Username	Problem	Language	Result	Execution time	Memory
646645		Vanilla	Sum Zero (RMI20_sumzero)	C++17	61 / 100	1045 ms	46808 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int maxn = 4e5 + 5;
const int lg = 17;
int64 a [maxn];
map <int64, int> ps;
int l [maxn];
int jump [maxn][lg];
 
int main() {
    int n;
    cin >> n;
    for (int i = 0; i <= n + 1; i++){
        l[i] = n + 1;
    }
    ps[0] = 0;
    int64 s = 0;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        s+=a[i];
        if (ps.count(s)) {
            l[ps[s] + 1] = i;
        }
        ps[s] = i;
    }
    for (int i = n; i >= 1; i--){
        l[i] = min(l[i], l[i + 1]);
        jump[i][0] = l[i];
    }
    for (int k = 1; k < lg; k++){
        jump[n + 1][k - 1] = n + 1;
        jump[n + 2][k - 1] = n + 1;
        for (int i = 1; i <= n; i++){
            jump[i][k] = jump[jump[i][k-1] + 1][k-1];
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        int rs = 0;
        for (int i = lg - 1; i >= 0; i--){
            while (jump[l][i] <= r) {
                rs+=(1 << i);
                l = jump[l][i] + 1;
            }
        }
        cout << rs << "\n";
    }
    
    
    // for (auto i: sv){
    //     cout << i.first << " " << i.second << "\n";
    // }
}

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