# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
947883 |
2024-03-17T08:00:14 Z |
pcc |
Sum Zero (RMI20_sumzero) |
C++17 |
|
195 ms |
19068 KB |
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
#pragma GCC target("avx2,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
const int B = 18;
const int mxn = 4e5+10;
int N,Q;
int dp[mxn];
int arr[mxn];
int ans[mxn];
pii req[mxn];
bool roll;
void calc(int lvl){
roll = 0;
for(int i = 1;i<=N+1;i++)dp[i] = arr[i];
dp[mxn-1] = mxn-1;
for(int i = 0;i<lvl;i++){
roll ^= 1;
for(int j = 1;j<=N+1;j++){
dp[j] = dp[dp[j]];
}
}
for(int i = 1;i<=Q;i++){
auto &[s,e] = req[i];
if(dp[s]<=e+1){
ans[i] += 1<<lvl;
s = dp[s];
}
}
return;
}
unordered_map<ll,int> mp;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>N;
for(int i = 1;i<=N;i++){
cin>>arr[i];
}
int mn = mxn-1;
ll sum = 0;
for(int i = N+1;i>=1;i--){
sum += arr[i];
if(mp.find(sum) != mp.end())mn = min(mn,mp[sum]);
mp[sum] = i;
arr[i] = mn;
}
cin>>Q;
for(int i = 1;i<=Q;i++){
cin>>req[i].fs>>req[i].sc;
}
for(int i = B-1;i>=0;i--)calc(i);
for(int i = 1;i<=Q;i++){
cout<<ans[i]<<'\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2652 KB |
Output is correct |
2 |
Correct |
2 ms |
604 KB |
Output is correct |
3 |
Correct |
2 ms |
2652 KB |
Output is correct |
4 |
Correct |
2 ms |
600 KB |
Output is correct |
5 |
Correct |
3 ms |
604 KB |
Output is correct |
6 |
Correct |
2 ms |
600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2652 KB |
Output is correct |
2 |
Correct |
2 ms |
604 KB |
Output is correct |
3 |
Correct |
2 ms |
2652 KB |
Output is correct |
4 |
Correct |
2 ms |
600 KB |
Output is correct |
5 |
Correct |
3 ms |
604 KB |
Output is correct |
6 |
Correct |
2 ms |
600 KB |
Output is correct |
7 |
Correct |
45 ms |
4536 KB |
Output is correct |
8 |
Correct |
41 ms |
4960 KB |
Output is correct |
9 |
Correct |
40 ms |
3412 KB |
Output is correct |
10 |
Correct |
40 ms |
4268 KB |
Output is correct |
11 |
Correct |
37 ms |
5804 KB |
Output is correct |
12 |
Correct |
40 ms |
3408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2652 KB |
Output is correct |
2 |
Correct |
2 ms |
604 KB |
Output is correct |
3 |
Correct |
2 ms |
2652 KB |
Output is correct |
4 |
Correct |
2 ms |
600 KB |
Output is correct |
5 |
Correct |
3 ms |
604 KB |
Output is correct |
6 |
Correct |
2 ms |
600 KB |
Output is correct |
7 |
Correct |
45 ms |
4536 KB |
Output is correct |
8 |
Correct |
41 ms |
4960 KB |
Output is correct |
9 |
Correct |
40 ms |
3412 KB |
Output is correct |
10 |
Correct |
40 ms |
4268 KB |
Output is correct |
11 |
Correct |
37 ms |
5804 KB |
Output is correct |
12 |
Correct |
40 ms |
3408 KB |
Output is correct |
13 |
Correct |
172 ms |
16584 KB |
Output is correct |
14 |
Correct |
169 ms |
18924 KB |
Output is correct |
15 |
Correct |
195 ms |
10892 KB |
Output is correct |
16 |
Correct |
180 ms |
19068 KB |
Output is correct |
17 |
Correct |
157 ms |
16072 KB |
Output is correct |
18 |
Correct |
172 ms |
10968 KB |
Output is correct |