oj.uz

Submission #875148

# Submission time Handle Problem Language Result Execution time Memory
875148 2023-11-18T17:47:42 Z Ahmed57 Sum Zero (RMI20_sumzero) C++17
100 / 100
 963 ms 19164 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
int P[400001][5];int vl[5];
int xd = 5;
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    vl[0] = 1;
    for(int i = 1;i<xd;i++){
        vl[i] = 5*vl[i-1];
    }
    int n,l,r,ans,x;
    cin>>n;
    unordered_map<long long,int> mp;
    long long sum = 0;
    mp[0] = 1;
    for(int i = 0;i<n;i++){
        cin>>x;
        sum+=x;
        if(mp[sum]>0){
            P[mp[sum]-1][0] = i+1;
        }
        mp[sum] = i+2;
    }
    for(int i = 0;i<=n;i++){
        if(P[i][0]==0)P[i][0] = n;
        else P[i][0]--;
    }
    for(int i = n;i>=0;i--){
        if(i<n)P[i][0] = min(P[i][0],P[i+1][0]);
        for(int j = 1;j<xd;j++){
            P[i][j] = P[min(n,P[min(n,P[min(n,P[min(n,P[i][j-1]+1)][j-1]+1)][j-1]+1)][j-1]+1)][j-1];
        }
    }
    int q;cin>>q;
    while(q--){
        cin>>l>>r;l--;r--;
        ans = 0;
        int e = xd-1;
        while(e>=0){
        while(P[l][e]<=r){
            l = P[l][e]+1;
            ans+=vl[e];
        }
        e--;
        }
        cout<<ans<<endl;
    }
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 600 KB Output is correct
2 Correct 7 ms 604 KB Output is correct
3 Correct 8 ms 528 KB Output is correct
4 Correct 8 ms 476 KB Output is correct
5 Correct 7 ms 604 KB Output is correct
6 Correct 7 ms 604 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 600 KB Output is correct
2 Correct 7 ms 604 KB Output is correct
3 Correct 8 ms 528 KB Output is correct
4 Correct 8 ms 476 KB Output is correct
5 Correct 7 ms 604 KB Output is correct
6 Correct 7 ms 604 KB Output is correct
7 Correct 156 ms 4744 KB Output is correct
8 Correct 151 ms 5292 KB Output is correct
9 Correct 170 ms 3644 KB Output is correct
10 Correct 156 ms 4592 KB Output is correct
11 Correct 143 ms 4328 KB Output is correct
12 Correct 159 ms 3552 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 600 KB Output is correct
2 Correct 7 ms 604 KB Output is correct
3 Correct 8 ms 528 KB Output is correct
4 Correct 8 ms 476 KB Output is correct
5 Correct 7 ms 604 KB Output is correct
6 Correct 7 ms 604 KB Output is correct
7 Correct 156 ms 4744 KB Output is correct
8 Correct 151 ms 5292 KB Output is correct
9 Correct 170 ms 3644 KB Output is correct
10 Correct 156 ms 4592 KB Output is correct
11 Correct 143 ms 4328 KB Output is correct
12 Correct 159 ms 3552 KB Output is correct
13 Correct 872 ms 16544 KB Output is correct
14 Correct 629 ms 18808 KB Output is correct
15 Correct 849 ms 10852 KB Output is correct
16 Correct 963 ms 19164 KB Output is correct
17 Correct 698 ms 16048 KB Output is correct
18 Correct 900 ms 10948 KB Output is correct