Submission #1076446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076446		IdanRosen	Sum Zero (RMI20_sumzero)	C++98	61 / 100	166 ms	65536 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef std::pair<ll, ll> pii;
typedef std::pair<ll, ll> pll;
typedef std::pair<ld, ld> pld;

#define MAXN 410000ll
#define LOGN ((ll) log2(MAXN) + 1ll)
int jump[MAXN][LOGN];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n;
    cin >> n;

    vector<ll> arr(n);
    for (auto &i: arr) cin >> i;

#define INF INT32_MAX
    vector<int> next(n, INF); {
        map<ll, set<int> > sums;
        vector<ll> pre_sum(n + 1);
        pre_sum[0] = 0;
        for (int i = 0; i < n; i++) {
            pre_sum[i + 1] = pre_sum[i] + arr[i];
            sums[pre_sum[i + 1]].insert(i + 1);
        }

        ll curr_sum = 0;
        for (int i = 0; i < n; i++) {
            if (sums.count(curr_sum)) {
                auto it = sums[curr_sum].upper_bound(i);
                if (it != sums[curr_sum].end()) next[i] = *it;
            }
            curr_sum += arr[i];
        }

        for (int i = n - 2; i >= 0; i--)
            next[i] = min(next[i], next[i + 1]);
    }

    for (int i = 0; i < n; i++) jump[i][0] = next[i];
    for (int k = 1; k < LOGN; k++)
        for (int i = 0; i < n; i++)
            jump[i][k] = ((jump[i][k - 1] == INF || jump[i][k - 1] == n) ? INF : jump[jump[i][k - 1]][k - 1]);

    int q;
    cin >> q;
    while (q-- > 0) {
        int l, r;
        cin >> l >> r;
        --l;

        int ans = 0;
        int curr = l;
        for (int k = LOGN - 1; k >= 0 && curr < n; k--) {
            if (jump[curr][k] <= r) {
                curr = jump[curr][k];
                ans += pow(2, k);
            }
        }

        cout << ans << "\n";
    }
}

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