Submission #597393

#	Time	Username	Problem	Language	Result	Execution time	Memory
597393		definitelynotmee	Sum Zero (RMI20_sumzero)	C++98	61 / 100	628 ms	39284 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 lift[10][400002];

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]];
    
    m.clear();
    s.clear();
    vector<int> last(n+2,0);
    last[pref[0]] = 1;
 
    for(int i = 2; i<= n+1; i++){
        lift[0][i] = max(last[pref[i]],lift[0][i-1]);
        last[pref[i]] = i;
    }
 
    for(int i = 1; i < 10; i++){
        for(int j = 1; j <= n+1; j++){
            lift[i][j] = lift[i-1][lift[i-1][lift[i-1][lift[i-1][j]]]];
        }
    }
 
    cin >> q;
 
    while(q--){
        int l, r;
        cin >> l >> r;
        int resp = 0;
        r++;
        for(int i = 9; i>= 0; i--){
            for(int j = 0; j < 3; j++)
                if(lift[i][r] >= l)
                    resp+=(1<<(2*i)), r = lift[i][r];
        }
        cout << resp << '\n';
    }
 
}

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