Submission #1228863

#TimeUsernameProblemLanguageResultExecution timeMemory
1228863rshohruhSum Zero (RMI20_sumzero)C++20
61 / 100
360 ms41200 KiB
// rshohruh #pragma GCC optimize("Ofast") #include <iostream> #include <algorithm> #include <vector> #include <map> #include <cmath> #ifdef LOCAL #include "debug.hpp" #else #define debug(...) 42 #endif using namespace std; #define ll long long // #define with_testcases void t_main(){ int n; cin >> n; vector<int> a(n+1); for(int i = 1; i <= n; ++i) cin >> a[i]; int log = 1; while((1<<log) <= n) log ++; vector up(log, vector(n+1, -1)); map<int, int> mp; mp[0] = 0; for(int i = 1, cur = 0, id = -1; i <= n; ++i) { cur += a[i]; if(mp.count(cur)) id = max(id, mp[cur]); up[0][i] = id; for(int j = 1; j < log; ++j) { if(up[j-1][i] != -1) up[j][i] = up[j-1][up[j-1][i]]; } mp[cur] = i; } int q; cin >> q; while(q--) { int l, r; cin >> l >> r; int ans = 0; for(int i = log-1; i >= 0; --i) { if(up[i][r] + 1 >= l) { ans += (1<<i); r = up[i][r]; } } cout << ans << '\n'; } } signed main(){ signed t = 1; cin.tie(nullptr)->sync_with_stdio(false); #ifdef with_testcases cin >> t; #endif while(t--){ t_main(); cout << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...