제출 #1118629

#제출 시각아이디문제언어결과실행 시간메모리
1118629peraSum Zero (RMI20_sumzero)C++17
61 / 100
200 ms25176 KiB
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 4e5 + 1; LL pre[N] , a[N]; int l[N] , r[N] , ans[N]; vector<int> lst(N) , o(N) , e; int main(){ cin.tie(0)->sync_with_stdio(0); int n; cin >> n; for(int i = 1;i <= n;i ++){ cin >> a[i]; } const int LOG = 19; LL pre[n + 1]; pre[0] = 0; for(int i = 1;i <= n;i ++){ pre[i] = pre[i - 1] + a[i]; } iota(o.begin() , o.end() , 0); sort(o.begin() , o.begin() + n + 1 , [&](int i , int j){ return pair<int , int>{pre[i] , i} < pair<int , int>{pre[j] , j}; }); for(int i = 0;i <= n;i ++){ int j = i; while(j <= n && pre[o[i]] == pre[o[j]]){ lst[o[j]] = (j > i ? o[j - 1] : -1); ++j; } i = j - 1; } for(int i = 1;i <= n;i ++){ lst[i] = max(lst[i] , lst[i - 1]); } int q; cin >> q; memset(ans , 0 , sizeof(ans)); for(int i = 0;i < q;i ++){ cin >> l[i] >> r[i]; } for(int bit = LOG - 1;bit >= 0;bit --){ e = lst; for(int c = 0;c < bit;c ++){ for(int i = n;i >= 0;i --){ e[i] = (e[i] > -1 ? e[e[i]] : -1); } } for(int i = 0;i < q;i ++){ if(e[r[i]] >= l[i] - 1){ ans[i] += 1 << bit; r[i] = e[r[i]]; } } } for(int i = 0;i < q;i ++){ cout << ans[i] << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...