제출 #495487

#제출 시각아이디문제언어결과실행 시간메모리
495487couplefireSum Zero (RMI20_sumzero)C++17
61 / 100
625 ms22284 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int N = 400005; int n, q, to[N][5]; map<ll, int> mp; ll sum; int main(){ // freopen("a.in", "r", stdin); cin.tie(0)->sync_with_stdio(0); cin >> n; mp[0] = 0; for(int i = 1; i<=n; ++i){ int a; cin >> a; sum += a; to[i][0] = to[i-1][0]; if(mp.count(sum)) to[i][0] = max(to[i][0], mp[sum]+1); mp[sum] = i; } mp.clear(); for(int j = 1; j<5; ++j) for(int i = 1; i<=n; ++i){ int bruh = i+1; for(int k = 0; k<16; ++k) bruh = to[bruh-1][j-1]; to[i][j] = bruh; } cin >> q; while(q--){ int l, r; cin >> l >> r; int cnt = 0, cur = r; for(int i = 4; i>=0; --i) while(to[cur][i]>=l) cur = to[cur][i]-1, cnt += (1<<(4*i)); cout << cnt << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...