Submission #846972

#	Time	Username	Problem	Language	Result	Execution time	Memory
846972		TahirAliyev	Sum Zero (RMI20_sumzero)	C++17	61 / 100	1027 ms	41044 KiB

sumzero

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long int
#define oo 1e9
#define pii pair<int, int>
 
const int MAX = 4e5 + 5, LOGMAX = 5; 
 
int n, q;
int arr[MAX];
int presum[MAX];
int R[MAX];
int E[MAX];
int par[LOGMAX][MAX];
set<pii> s;
 
ll lift(int t, int f){
    ll ans = 0;
    for(int j = LOGMAX - 1; j >= 0 && par[0][t] != 0; j--){
        while(par[j][t] <= f && par[j][t] != 0){
            t = par[j][t];
            ans += (1 << (j * 3));
        }
    }
    if(par[0][t] <= f + 1 && par[0][t] != 0) ans++;
    return ans;
}
 
int main(){
    cin >> n;
    s.insert({0, 0});
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
        presum[i] = presum[i - 1] + arr[i];
        s.insert({presum[i], i});
    }
    for(int l = 0; l < n; l++){
        s.erase(s.find({presum[l], l}));
        auto itr = s.lower_bound({presum[l], 0});
        if(itr == s.end() || (*itr).first != presum[l]) continue;
        R[l + 1] = (*itr).second;
    }
    cin >> q;
    s.clear();
    for(int i = 1; i <= n; i++){
        if(R[i]) s.insert({R[i], i});
    }
    for(int i = 1; i <= n; i++){
        if(R[i - 1] && i){
            s.erase(s.find({R[i - 1], i - 1}));
        }
        E[i] = (*s.begin()).first;
    }
    for(int i = 1; i <= n; i++){
        if(!E[i]){
            par[0][i] = 0;
            continue;
        }
        par[0][i] = E[i] + 1;
    }
    for(int j = 1; j < LOGMAX; j++){
        for(int i = 1; i <= n; i++){
            par[j][i] = par[j - 1][par[j - 1][par[j - 1][par[j - 1][par[j - 1][par[j - 1][par[j - 1][par[j - 1][i]]]]]]]];
        }
    }
    while(q--){
        int l, r; cin >> l >> r;
        cout << lift(l, r) << '\n';
    }
}

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