Submission #1136238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136238		hypersphere	Sum Zero (RMI20_sumzero)	C++20	61 / 100	327 ms	45356 KiB

sumzero

// This is your sign to stop stalking
// Save at User name to source repo

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <string>
#include <stack>
#include <cstring>
#include <cstdio>
#include <ctime>
#include <iomanip>
#include <numeric>
#include <stdio.h>
#include <cstdlib>

#pragma region Helpers
#define printArr(a) for(int i = 0; i < a.size(); i++) cout << a[i] << " "; cout << "\n";
#define printArrWithComma(a) for(int i = 0; i < a.size(); i++) cout << a[i] << ", "; cout << "\n";
#define printArrIgnore0(a) for(int i = 1; i < a.size(); i++) cout << a[i] << " "; cout << "\n";
#define checkpoint(n) cout << "Checkpoint " << n << "\n";


using namespace std;

long long binpow(long long base, long long power, long long mod) {
    if (base == 0) return 0;
    if (base == 1) return 1;
    if (power == 0) return 1;
    long long multiplier = (power % 2 == 0 ? 1 : base);
    return (binpow((base * base) % mod, power / 2, mod) * multiplier) % mod;
}
const long long mod = 1000000007;
long long gcd(long long a, long long b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
long long factorial(long long n) {
    long long ans = 1;
    for (long long i = 1; i <= n; i++) ans *= i;
    return ans;
}
const long long INF = 1000000000000000;
#pragma endregion

int lg;
void Run() {
    int n;
    cin >> n;
    lg = ceil(log2(n));
    vector<int> arr(n + 1);
    long long pref = 0;
    vector<vector<int>> up(lg + 1, vector<int>(n + 1, -1));
    map<long long, int> mp;
    mp[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        pref += arr[i];
        up[0][i] = up[0][i - 1];
        if (mp.count(pref)) {
            up[0][i] = max(up[0][i - 1], mp[pref]);
        }
        mp[pref] = i;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= lg; j++) {
            if (up[j - 1][i] == -1) continue;
            up[j][i] = up[j - 1][up[j - 1][i]];
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        int ans = 0;
        for (int i = lg; i >= 0; i--) {
            if (r == -1) break;
            if (up[i][r] < l - 1) continue;
            int t = r;
            ans += (1 << i);
            r = up[i][r];
            //cout << "Took " << (1 << i) << " from " << t << " to " << r << "\n";
        }
        cout << ans << "\n";
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tests = 1;
    //cin >> tests;
    auto start = clock();
    while (tests--) Run();
    auto end = clock();
    cerr << "Time: " << end - start << " (ms)\n";
}

/* 
5 3
1 5 4
2 3 5
1 2 4
*/
// Code by an idiot

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