Submission #1316219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316219		sefat	Sum Zero (RMI20_sumzero)	C++20	61 / 100	377 ms	48656 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]; // prefix sum
    }

    int INF_IDX = n + 2;
    map<long long, int> mp;
    vector<vector<int>> jump(21, vector<int>(n+3, INF_IDX));

    jump[0][n+1] = INF_IDX;
    mp[pr[n]] = n + 1;
    int pos_zero = INF_IDX;

    for (int i = n; i >= 1; --i) {
        if (a[i] == 0) pos_zero = i + 1;
        int best = jump[0][i+1];
        auto it = mp.find(pr[i-1]);
        if (it != mp.end()) best = min(best, it->second);
        best = min(best, pos_zero);
        jump[0][i] = best;
        mp[pr[i]] = i + 1;
    }

    for (int j = 1; j <= 20; ++j) {
        for (int i = 1; i <= n+1; ++i) {
            int nxt = jump[j-1][i];
            jump[j][i] = (nxt <= n+1) ? jump[j-1][nxt] : INF_IDX;
        }
    }

    int q;
    cin >> q;
    while(q--) {
        int l, r;
        cin >> l >> r;
        int cur = l;
        int ans = 0;
        for (int j = 20; j >= 0; --j) {
            if (cur <= n+1 && jump[j][cur] <= r+1) {
                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;
}

Compilation message (stderr)

sumzero.cpp:192:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
  192 | const int INF = 1e18;
      |                 ^~~~

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