이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |