Submission #597406

#	Time	Username	Problem	Language	Result	Execution time	Memory
597406		definitelynotmee	Sum Zero (RMI20_sumzero)	C++98	100 / 100	571 ms	18252 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[4][400002];

int main(){
    
    cin.tie(0)->sync_with_stdio(0);
 
    int n, q;
    cin >> n;
 
    vector<ll> pref(n+2);
    vector<ll> pref2;
 
    for(int i = 2; i <= n+1; i++){
        cin >> pref[i];
        pref[i]+=pref[i-1];

    }
    
    pref2 = pref;
    sort(all(pref2));
    pref2.erase(unique(all(pref2)),pref2.end());
    
    for(int i = 0; i <= n+1; i++)
        pref[i] = lower_bound(all(pref2),pref[i])-pref2.begin();
    
    pref2.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 < 4; i++){
        for(int j = 1; j <= n+1; j++){
            lift[i][j] = lift[i-1][j];
            for(int k = 0; k < 31; k++)
                lift[i][j] = lift[i-1][lift[i][j]];
        }
    }
 
    cin >> q;
 
    while(q--){
        int l, r;
        cin >> l >> r;
        int resp = 0;
        r++;
        for(int i = 3; i>= 0; i--){
            for(int j = 0; j < 31; j++){
                if(lift[i][r] >= l)
                    resp+=(1<<(5*i)), r = lift[i][r];
                else break;
            }
        }
        cout << resp << '\n';
    }
 
}

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