제출 #970914

#제출 시각아이디문제언어결과실행 시간메모리
970914lmaobruhSum Zero (RMI20_sumzero)C++14
61 / 100
383 ms22100 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int N = 4e5 + 5; int n, q, ku[N][6]; map<ll, int> mp; void build_rmq() { int cur, ti; for (int j = 1; j <= 5; ++j) for (int i = 1; i + (1 << (j * 2)) - 1 <= n; ++i) { cur = i; for (int ti = 1; ti <= 16; ++ti) { cur = ku[cur][j - 1]; if (cur == 0) break; else cur++; } if (cur == 0) { ku[i][j] = 0; continue; } ku[i][j] = cur - 1; } } void build() { cin >> n; ll sum = 0, x; mp[0] = 0; for (int i = 1; i <= n; ++i) ku[i][0] = -1; for (int i = 1; i <= n; ++i) { cin >> x; sum += x; if (mp.count(sum)) ku[mp[sum] + 1][0] = i; mp[sum] = i; } mp.clear(); int pre = -1; for (int i = n; i >= 1; --i) { if (ku[i][0] != -1) pre = (pre == -1 ? ku[i][0] : min(pre, ku[i][0])); else ku[i][0] = 0; ku[i][0] = (pre != -1 ? pre : 0); } build_rmq(); } int ans; int que(int l, int r) { ans = 0; for (int i = 4; i >= 0; --i) while (ku[l][i] != 0 && ku[l][i] <= r) { ans += 1 << (i * 4); l = ku[l][i] + 1; } return ans; } void ouput() { cin >> q; while (q--) { static int l, r; cin >> l >> r; cout << que(l, r) << '\n'; } } void solve() { build(); ouput(); } signed main() { cin.tie(0) -> sync_with_stdio(0); solve(); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

sumzero.cpp: In function 'void build_rmq()':
sumzero.cpp:11:12: warning: unused variable 'ti' [-Wunused-variable]
   11 |   int cur, ti;
      |            ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...