Submission #920523

#	Time	Username	Problem	Language	Result	Execution time	Memory
920523		imarn	Sum Zero (RMI20_sumzero)	C++14	61 / 100	422 ms	49424 KiB

sumzero

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define vp vector<pii>
using namespace std;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    int a[n+1];
    int pr[n+2][21];for(int i=0;i<=n+1;i++)pr[i][0]=-1;
    for(int i=1;i<=n;i++)cin>>a[i];
    unordered_map<int,int>um;int sum=0;
    int id=0;um[0]=0;
    for(int i=1;i<=n;i++){
        sum+=a[i];
        if(um.find(sum)!=um.end()){
            while(id<=um[sum])pr[id++][0]=i;
        }um[sum]=i;
    }
    for(int i=0;i<=n+1;i++)if(pr[i][0]==-1)pr[i][0]=n+1;
    for(int j=1;j<=20;j++)for(int i=0;i<=n+1;i++)pr[i][j]=pr[pr[i][j-1]][j-1];
    int q;cin>>q;
    while(q--){
        int l,r;cin>>l>>r;l--;
        int res=0;
        for(int i=20;i>=0;i--){
            if(pr[l][i]<=r)res+=(1<<i),l=pr[l][i];
        }cout<<res<<'\n';
    }
}

• Subtask 1: 22 / 22
• Subtask 2: 39 / 39
• Subtask 3: 0 / 39