Submission #597349

#	Time	Username	Problem	Language	Result	Execution time	Memory
597349		definitelynotmee	Sum Zero (RMI20_sumzero)	C++98	61 / 100	680 ms	56168 KiB

sumzero

#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename t>
using matrix = vector<vector<t>>;

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

    int n, q;
    cin >> n;

    vector<ll> pref(n+2);
    set<ll> s = {0};
    map<ll,ll> m;

    for(int i = 2; i <= n+1; i++){
        cin >> pref[i];
        pref[i]+=pref[i-1];
        s.insert(pref[i]);
    }

    for(ll i : s){
        m[i] = m.size();
    }

    for(int i = 0; i <= n+1; i++)
        pref[i] = m[pref[i]];

    vector<int> last(n+2,0);
    last[m[0]] = 1;

    matrix<int> lift(20,vector<int>(n+2));

    for(int i = 2; i<= n+1; i++){
        lift[0][i] = max(last[pref[i]],lift[0][i-1]);
        last[pref[i]] = i;
        //cout << lift[0][i] -1 << ' ';
    }
    //cout << '\n';

    for(int i = 1; i < 20; i++){
        for(int j = 1; j <= n+1; j++){
            lift[i][j] = lift[i-1][lift[i-1][j]];
        }
    }

    cin >> q;

    while(q--){
        int l, r;
        cin >> l >> r;
        int resp = 0;
        r++;
        for(int i = 19; i>= 0; i--){
            if(lift[i][r] >= l)
                resp+=(1<<i), r = lift[i][r];
        }
        cout << resp << '\n';
    }

}

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