Submission #750323

#	Time	Username	Problem	Language	Result	Execution time	Memory
750323		doowey	Sum Zero (RMI20_sumzero)	C++14	61 / 100	446 ms	26628 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)4e5 + 4;
const int B = 5;

int nex[B][N];
int pwr[B];

int main(){
    fastIO;
    //freopen("in.txt", "r", stdin);
    int n;
    cin >> n;
    int a;
    map<ll, int> pre;
    pre[0ll] = 0;
    pwr[0] = 1;
    nex[0][0] = -1;
    int st = -1;
    ll sum = 0;

    for(int i = 1; i <= n ; i ++ ){
        cin >> a;
        sum += a;
        if(pre.count(sum)){
            st=max(st,pre[sum]);
        }
        nex[0][i] = st;
        pre[sum]=i;
    }
    int g;
    for(int ln = 1; ln < B; ln ++ ){
        pwr[ln] = pwr[ln - 1] * 16;
        for(int i = 0 ; i <= n; i ++ ){
            g = i;
            for(int j = 0 ; j < 16; j ++ ){
                if(g == -1) break;
                g = nex[ln - 1][g];
            }
            nex[ln][i] = g;
        }
    }

    int q;
    cin >> q;
    int lf, rf;
    for(int iq = 1; iq <= q; iq ++ ){
        cin >> lf >> rf;
        lf -- ;
        g = 0;
        for(int ln = B - 1; ln >= 0 ; ln -- ){
            while(nex[ln][rf] >= lf){
                g += pwr[ln];
                rf = nex[ln][rf];
            }
        }
        cout << g << "\n";
    }
    return 0;
}

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