제출 #1098278

#제출 시각아이디문제언어결과실행 시간메모리
1098278NeltSum Zero (RMI20_sumzero)C++17
61 / 100
315 ms43860 KiB
// #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx,avx2,fma") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define endl "\n" using namespace std; using namespace __gnu_pbds; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); template <typename T, typename key = less<T>> using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>; const int lg = 19, N = 4e5 + 5; int up[lg][N]; void solve() { int n; cin >> n; int a[n + 1]; for (int i = 1; i <= n; i++) cin >> a[i]; map<ll, int> last; int mn = n + 1; ll sum = 0; last[0] = n + 1; for (int i = n; i >= 1; i--) { last[sum] = i; sum += a[i]; if (last.count(sum)) mn = min(mn, last[sum]); up[0][i] = mn + 1; } // for (int i = 1; i <= n; i++) cout << up[0][i] << " \n"[i == n]; for (int i = 0; i < lg; i++) up[i][n + 2] = up[i][n + 1] = n + 2; for (int bit = 1; bit < lg; bit++) for (int i = 1; i <= n; i++) up[bit][i] = min((int)n + 2, up[bit - 1][up[bit - 1][i]]); int q; cin >> q; // cout << up[18][1] << endl; while (q--) { int l, r; cin >> l >> r; int ans = 0; for (ll bit = lg - 1; bit >= 0; bit--) if (up[bit][l] <= r + 1) ans += 1 << bit, l = up[bit][l]; cout << ans << endl; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); ll t = 1; // precomp(); // cin >> t; for (ll cs = 1; cs <= t; cs++) solve(); // cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...