Submission #1316217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316217		sefat	Sum Zero (RMI20_sumzero)	C++20	0 / 100	3 ms	1336 KiB

sumzero

#pragma GCC optimize("O3,unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

// ----------- Fast Typing ------------
#define int long long
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define vi vector<int>
#define ii pair<int, int>
#define vii vector<ii>
#define yes cout << "YES\n"
#define no cout << "NO\n"

// ----------- Ordered Set (policy-based) ------------
template <typename T>
using ordered_set = tree<
    T,
    null_type,
    less<T>,
    rb_tree_tag,
    tree_order_statistics_node_update
>;

#ifndef ONLINE_JUDGE

// Forward declarations of print helpers
void _print(const string &s);
void _print(const char *s);
void _print(char c);
void _print(bool x);
void _print(long double x);
void _print(long x);
void _print(int x);

// Pair
template<typename T, typename V>
void _print(const pair<T, V> &p) {
    cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}";
}

// Tuple
template<class Tuple, size_t... I>
void _print_tuple(const Tuple &t, std::index_sequence<I...>) {
    cerr << "(";
    (( _print(get<I>(t)), cerr << (I + 1 == sizeof...(I) ? "" : ", ") ), ...);
    cerr << ")";
}

template<typename... Ts>
void _print(const tuple<Ts...> &t) {
    _print_tuple(t, std::index_sequence_for<Ts...>{});
}

// Vector
template<typename T>
void _print(const vector<T> &v) {
    cerr << "[";
    for (size_t i = 0; i < v.size(); ++i) {
        _print(v[i]);
        if (i + 1 < v.size()) cerr << ", ";
    }
    cerr << "]";
}

// Deque
template<typename T>
void _print(const deque<T> &v) {
    cerr << "[";
    for (size_t i = 0; i < v.size(); ++i) {
        _print(v[i]);
        if (i + 1 < v.size()) cerr << ", ";
    }
    cerr << "]";
}

// List
template<typename T>
void _print(const list<T> &l) {
    cerr << "[";
    bool first = true;
    for (auto &x : l) {
        if (!first) cerr << ", ";
        _print(x);
        first = false;
    }
    cerr << "]";
}

// Set
template<typename T>
void _print(const set<T> &s) {
    cerr << "{";
    bool first = true;
    for (auto &x : s) {
        if (!first) cerr << ", ";
        _print(x);
        first = false;
    }
    cerr << "}";
}

// Unordered set
template<typename T>
void _print(const unordered_set<T> &s) {
    cerr << "{";
    bool first = true;
    for (auto &x : s) {
        if (!first) cerr << ", ";
        _print(x);
        first = false;
    }
    cerr << "}";
}

// Map
template<typename T, typename V>
void _print(const map<T, V> &m) {
    cerr << "{";
    bool first = true;
    for (auto &kv : m) {
        if (!first) cerr << ", ";
        _print(kv);
        first = false;
    }
    cerr << "}";
}

// Unordered map
template<typename T, typename V>
void _print(const unordered_map<T, V> &m) {
    cerr << "{";
    bool first = true;
    for (auto &kv : m) {
        if (!first) cerr << ", ";
        _print(kv);
        first = false;
    }
    cerr << "}";
}

// C-style string
void _print(const char *s) { cerr << '"' << s << '"'; }
void _print(const string &s) { cerr << '"' << s << '"'; }
void _print(char c) { cerr << '\'' << c << '\''; }
void _print(bool x) { cerr << (x ? "true" : "false"); }

// Numbers
void _print(long double x) { cerr << (double)x; }
void _print(long x) { cerr << x; }
void _print(int x) { cerr << x; }

// Generic fallback for pointers / other printable types
template<typename T>
void _print(const T* p) {
    if (p == nullptr) cerr << "nullptr";
    else cerr << "ptr(" << (void*)p << ")";
}

// Variadic debug printer
void _debug() { cerr << '\n'; }

template<typename Head, typename... Tail>
void _debug(Head H, Tail... T) {
    _print(H);
    if constexpr (sizeof...(T) > 0) cerr << ", ";
    _debug(T...);
}

#define debug(...) cerr << "[" << __FILE__ << ":" << __LINE__ << "] " << "[" << #__VA_ARGS__ << "] = ", _debug(__VA_ARGS__)

#else
    #define debug(...) ((void)0)
#endif

// ----------- Random Generator ------------
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int randInt(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

// ----------- Constants ------------
const int MOD = 1e9 + 7;
const int INF = 1e18;
const int N = 2e5 + 5;

// ----------- Useful Functions ------------
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int lcm(int a, int b) { return (a / gcd(a, b)) * b; }

// ----------- Main Solve Function ------------
void solve() {
    int n;
    if (!(cin >> n)) return;
    vi a(n+1), pr(n+1, 0);

    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        pr[i] = pr[i-1] + a[i]; // clearer prefix sum
    }

    map<int, int> mp;
    // use n+2 sized jump to safely index up to n+1
    vector<vector<int>> jump(21, vector<int>(n+2, -1));

    // initialize all to -1 (already done)
    jump[0][n] = n + 1;
    mp[pr[n]] = n;

    int pos_zero = n+1;
    if(a[n] == 0) pos_zero = n;

    for(int i = n - 1; i >= 1; --i) {


        if (mp.find(pr[i-1]) == mp.end()) jump[0][i] = min(jump[0][i+1], pos_zero);
        else {
            jump[0][i] = min({jump[0][i+1], mp[pr[i-1]], pos_zero});
        }
        // debug(i, mp[i], jump[0][i]);
        if(a[i] == 0) pos_zero = i;
        mp[pr[i]] = i;
    }

    // build binary lifting table
    for(int j = 1; j <= 20; ++j) {
        for(int i = 1; i <= n; ++i) {
            if (jump[j-1][i] != -1) {
                int nxt = jump[j-1][i];
                jump[j][i] = (nxt <= n+1) ? jump[j-1][nxt] : -1;
            }
        }
    }

    // for(int i=1; i<=n; i++) {
    //     debug(i);
    //     debug(jump[0][i], jump[1][i], jump[2][i]);
    // }

    int q;
    cin >> q;
    while(q--) {
        int l, r;
        cin >> l >> r;
        int cur = l, ans = a[cur] == 0;
        // debug(cur);

        for(int j = 20; j >= 0; --j) {
            // debug(cur, j, jump[j][cur]);
            if (jump[j][cur] != -1 && jump[j][cur] <= r) {
                ans += (1LL << j);
                cur = jump[j][cur];
            }
        }

        cout << ans << '\n';
    }
}

// ----------- Main Function ------------
int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    // cin >> t;

    for(int i = 1; i <= t; ++i) {
        solve();
    }

    return 0;
}

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