Submission #1076387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076387		IdanRosen	Sum Zero (RMI20_sumzero)	C++98	22 / 100	105 ms	29504 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;

template<typename T, typename D>
class sparse_table {
private:
    size_t n;
    size_t logn;
    vector<vector<D> > table;
    vector<size_t> lg;

    D (*convert)(const T &);

    T (*function)(const T &, const T &);

public:
    sparse_table(const vector<T> &arr, D (*conv)(const T &), T (*func)(const T &, const T &)) : n(arr.size()),
        logn(log2(n) + 1),
        convert(conv), function(func) {
        table.resize(logn, vector<T>(n));
        for (size_t i = 0; i < n; i++)
            table[0][i] = convert(arr[i]);

        for (size_t k = 1; k < logn; k++)
            for (size_t i = 0; i + (1 << k) <= n; i++)
                table[k][i] = function(table[k - 1][i], table[k - 1][i + (1 << (k - 1))]);

        // lg[i] stores and biggest i such that
        // 2^i is smaller or equal to i
        lg.resize(n + 1);
        for (size_t i = 1; i <= n; i++)
            lg[i] = (1 + log2(i)) - 1;
    }

    // query that merges two (may) overlapping ranges
    T query_overlap(size_t l, size_t r) {
        // [l, r)
        size_t pow = lg[r - l];

        return function(
            table[pow][l],
            table[pow][r - (1 << pow)]
        );
    }

    // qeury that merges non overlapping ranges
    T query_nooverlap(size_t l, size_t r) {
        // [l, r)
        bool empty = true;
        T ans;

        size_t curr_l = l;
        for (ssize_t k = logn - 1; k >= 0; k--) {
            size_t sz = 1 << k;

            if (sz <= r - curr_l) {
                if (empty) {
                    ans = table[k][curr_l];
                    empty = false;
                } else
                    ans = function(ans, table[k][curr_l]);

                curr_l += sz;
            }
        }

        return ans;
    }
};


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;

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

    vector<ll> next(n, LLONG_MAX);
    ll curr_sum = 0;
    for (ll 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 (ll i = n - 2; i >= 0; i--)
        next[i] = min(next[i], next[i + 1]);

    ll logn = log2(n) + 1;
    vector<vector<ll> > jump(n, vector<ll>(logn));
    for (ll i = 0; i < n; i++) jump[i][0] = next[i];
    for (ll k = 1; k < logn; k++)
        for (ll i = 0; i < n; i++)
            jump[i][k] = ((jump[i][k - 1] == LLONG_MAX || jump[i][k - 1] == n) ? LLONG_MAX : jump[jump[i][k - 1]][k - 1]);

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

        ll ans = 0;
        ll curr = l;
        for (ll 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: 0 / 39
• Subtask 3: 0 / 39