제출 #874723

#제출 시각아이디문제언어결과실행 시간메모리
874723Mizo_CompilerSum Zero (RMI20_sumzero)C++17
61 / 100
437 ms50008 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef double ld; #define pb push_back #define sz(x) int(x.size()) #define all(x) x.begin(),x.end() #define F first #define S second const int N = 4e5+5; int n, a[N], up[N][19]; int main () { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; map<ll, int> ls; ll sum = 0; for (int i = 0; i < n; i++) { up[i][0] = n; } up[n][0] = n; for (int i = 0; i < n; i++) { cin >> a[i]; ls[sum] = i; if (ls.count(sum+a[i])) { up[ls[sum+a[i]]][0] = min(up[ls[sum+a[i]]][0], i); } sum += a[i]; } for (int i = n-2; i >= 0; i--) { up[i][0] = min(up[i][0], up[i+1][0]); } for (int i = 1; i < 19; i++) { for (int j = 0; j < n; j++) { if (up[j][i-1] == n) { up[j][i] = n; continue; } up[j][i] = up[up[j][i-1]+1][i-1]; } up[n][i] = n; } int q; cin >> q; while (q--) { int l, r; cin >> l >> r; --l, --r; int cnt = 0; for (int i = 18; i >= 0; i--) { if (up[l][i] <= r) { cnt += (1 << i); l = up[l][i]+1; } } cout << cnt << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...