Submission #946154

#TimeUsernameProblemLanguageResultExecution timeMemory
946154dubabubaSum Zero (RMI20_sumzero)C++14
61 / 100
1004 ms17248 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("unroll-loops") #pragma GCC optimize("O3,no-stack-protector,conserve-stack") #pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt") typedef pair<int, int> pii; #define ff first #define ss second #define MP make_pair const int LOG = 3; const int base = 74; const int mxn = 4e5 + 10; int i, j, n, m; long long pref; map<long long, int> mp; int stab[mxn][LOG]; int pw[LOG]; int main() { #ifdef LOCAL auto start = chrono::high_resolution_clock::now(); #endif cin.tie(0)->sync_with_stdio(0); cin >> n; mp[0] = 0; for(i = 1; i <= n; i++) { cin >> j; pref += j; auto it = mp.find(pref); if(it != mp.end()) { stab[it->ss + 1][0] = i; } mp[pref] = i; } mp.clear(); for(i = n; i > 0; i--) { if(stab[i][0] == 0) stab[i][0] = stab[i + 1][0]; else if(stab[i + 1][0] > 0) stab[i][0] = min(stab[i][0], stab[i + 1][0]); } int cur, b; for(j = 1; j < LOG; j++) for(i = 1; i <= n; i++) { cur = stab[i][j - 1]; for(b = 1; b < base; b++) { if(cur > 0 && cur + 1 <= n) cur = stab[cur + 1][j - 1]; else { cur = 0; break; } } stab[i][j] = cur; } pw[0] = 1; for(int i = 1; i < LOG; i++) pw[i] = pw[i - 1] * base; cin >> m; int l, r, ans; while(m--) { cin >> l >> r; ans = 0; for(j = LOG - 1; j >= 0; j--) { while(stab[l][j] > 0 && stab[l][j] <= r) { l = stab[l][j] + 1; ans += pw[j]; } } cout << ans << endl; } #ifdef LOCAL auto end = chrono::high_resolution_clock::now(); for(int i = 0; i <= 20; ++i) cout << '-'; cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl; #endif return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...