제출 #549278

#제출 시각아이디문제언어결과실행 시간메모리
549278kevinxiehkSum Zero (RMI20_sumzero)C++17
61 / 100
379 ms29900 KiB
#include <bits/stdc++.h> #define mp make_pair #define pb emplace_back #define fi first #define se second // #define int long long #define inf 1e9 #define ick cout<<"ickbmi32.9\n" using namespace std; int sps[400005]; int qus[400005][3]; int nxt[400005]; long long ps; signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; map<long long, int> la; int t; for(int i = 1; i <= n; i++) { cin >> t; ps += t; nxt[i] = n + 1; if(la[ps] != 0 || ps == 0) { nxt[la[ps] + 1] = min(nxt[la[ps] + 1], i); } la[ps] = i; } for(int i = n - 1; i >= 1; i--) { nxt[i] = min(nxt[i], nxt[i + 1]); } // for(int i = 1; i <= n; i++) { // cout << next[i] << ' '; // }cout << '\n'; //return 0; nxt[n + 1] = n + 1; nxt[n + 2] = n + 1; for(int i = 1; i <= n + 2; i++) { sps[i] = nxt[i]; } int q; cin >> q; for(int i = 0; i < q; i++) { cin >> qus[i][0] >> qus[i][1]; qus[i][2] = 0; } for(int k = 19; k >= 0; k--) { for(int i = 1; i <= n + 2; i++) { sps[i] = nxt[i]; } for(int j = 1; j <= k; j++) { for(int i = 1; i <= n + 2; i++) { sps[i] = sps[sps[i] + 1]; if(sps[i] > n) sps[i] = n + 1; // cout << sps[i][j] << ' '; } // cout << '\n'; }//return 0; for(int i = 0; i < q; i++) { if(sps[qus[i][0]] <= qus[i][1]) { qus[i][0] = sps[qus[i][0]] + 1; qus[i][2] += (1 << k); } } } // while(q--) { // int l, r; // cin >> l >> r; // int ans = 0; // for(int i = 19; i >= 0; i--) { // if(sps[l][i] <= r) { // ans += (1 << i); // l = sps[l][i] + 1; // } // } // cout << ans << '\n'; // } for(int i = 0; i < q; i++) cout << qus[i][2] << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...