Submission #748423

#	Time	Username	Problem	Language	Result	Execution time	Memory
748423		doowey	Sum Zero (RMI20_sumzero)	C++14	61 / 100	601 ms	51780 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, 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 + 10;
const int LOG = 19;

ll c[N];

int jump[LOG][N];

int main(){
    fastIO;
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++ ){
        cin >> c[i];
    }
    ll suff = 0;
    map<ll, int> en;
    en[0ll] = n + 1;
    for(int ln = 0 ; ln < LOG; ln ++ ){
        for(int i = 1; i <= n + 1; i ++ ){
            jump[ln][i] = -1;
        }
    }
    int id;
    int low = n + 2;
    for(int i = n; i >= 1; i -- ){
        suff += c[i];
        if(en.count(suff)){
            low = min(low, en[suff]);
        }
        if(low < n + 2)
            jump[0][i] = low;
        en[suff] = i;
    }
    for(int ln = 1; ln < LOG; ln ++ ){
        for(int i = 1 ; i <= n; i ++ ){
            if(jump[ln - 1][i] != -1){
                jump[ln][i] = jump[ln - 1][jump[ln - 1][i]];
            }
        }
    }
    int q;
    cin >> q;
    int li, ri;
    int ans;
    for(int iq = 1; iq <= q; iq ++ ){
        cin >> li >> ri;
        ans = 0;
        for(int ln = LOG - 1; ln >= 0 ; ln -- ){
            if(jump[ln][li] == -1) continue;
            if(jump[ln][li] <= ri + 1){
                li = jump[ln][li];
                ans += (1 << ln);
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

Compilation message (stderr)

sumzero.cpp: In function 'int main()':
sumzero.cpp:35:9: warning: unused variable 'id' [-Wunused-variable]
   35 |     int id;
      |         ^~

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