Submission #1225653

#TimeUsernameProblemLanguageResultExecution timeMemory
1225653Sir_Ahmed_ImranSum Zero (RMI20_sumzero)C++17
61 / 100
268 ms45444 KiB
// 01001100 01001111 01010100 01000001 \\ // \\ // ╦ ╔═╗╔╦╗╔═╗ \\ // ║ ║ ║ ║ ╠═╣ \\ // ╩═╝╚═╝ ╩ ╩ ╩ \\ // \\ // 01001100 01001111 01010100 01000001 \\ #include <bits/stdc++.h> using namespace std; #define N 400001 #define nl '\n' #define ff first #define ss second #define add insert #define ll long long #define ld long double #define terminator main #define pll pair<ll,ll> #define append push_back #define pii pair<int,int> #define all(x) (x).begin(),(x).end() #define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) ll a[N]; int x[N][19]; map<ll, int> p; void solve(){ int n, q, l, r, ans; cin >> n; p[0] = 1; for(int i = 1; i <= n; i++){ cin >> a[i]; x[i][0] = n + 2; a[i] += a[i - 1]; x[p[a[i]]][0] = i + 1; p[a[i]] = i + 1; } for(int i = n - 1; i > 0; i--) x[i][0] = min(x[i][0], x[i + 1][0]); for(int j = 0; j < 19; j++) x[n + 1][j] = x[n + 2][j] = n + 2; for(int j = 0; j < 18; j++) for(int i = 1; i <= n; i++) x[i][j + 1] = x[x[i][j]][j]; cin >> q; while(q--){ cin >> l >> r; r++; ans = 0; for(int i = 18; i >= 0; i--){ if(x[l][i] <= r){ ans += (1 << i); l = x[l][i]; } } cout << ans << nl; } } int terminator(){ L0TA; solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...