제출 #942760

#제출 시각아이디문제언어결과실행 시간메모리
942760ShadowSharkSum Zero (RMI20_sumzero)C++17
61 / 100
598 ms23704 KiB
#include <bits/stdc++.h> using namespace std; const int maxN = 4e5 + 9; int jump[9][maxN]; pair<int, int> *segment; pair<long long, int> *sum; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; segment = new pair<int, int>[n + 1]; sum = new pair<long long, int>[n + 1]; sum[0] = {0, 0}; for (int i = 1; i <= n; i++) { int x; cin >> x; sum[i] = {sum[i - 1].first + x, i}; } sort(sum, sum + n + 1); int cnt = 0; for (int i = 0; i < n; i++) { //cout << sum[i].first << ' ' << sum[i].second << '\n'; if (sum[i].first == sum[i + 1].first) segment[++cnt] = {sum[i + 1].second, sum[i].second + 1}; } delete[] sum; sort(segment + 1, segment + cnt + 1); int curr = 0; jump[0][n + 1] = n + 1; for (int i = 0; i <= n; i++) { while (curr <= cnt && i >= segment[curr].second) curr++; if (curr > cnt) jump[0][i] = n + 1; else jump[0][i] = segment[curr].first; } delete[] segment; for (int i = 1; i <= 8; i++) for (int j = 0; j <= n + 1; j++) jump[i][j] = jump[i - 1][jump[i - 1][j]]; int q; cin >> q; while (q--) { int l, r; cin >> l >> r; int ans = 0; l--; for (int i = 8; i >= 0; i--) while (jump[i][l] <= r) { l = jump[i][l]; ans += 1 << i; } cout << ans << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...