Submission #1342066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1342066		po_rag526	Sum Zero (RMI20_sumzero)	C++20	0 / 100	2 ms	1348 KiB

sumzero

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,c[400005],q,l,r,nxt[400005][25],pw[30];
map<ll,ll>mp;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cin.tie(0);
    cin>>n;
    pw[0]=1;
    nxt[n+1][0]=n+1;
    for(int i=1;i<=25;i++){
        pw[i]=pw[i-1]*2;
        nxt[n+1][i]=n+1;
    }
    for(int i=1;i<=n;i++){
        cin>>c[i];
        c[i]+=c[i-1];
        if (mp[c[i]]!=0)nxt[mp[c[i]]][0]=i;
        if (c[i]==0 && mp[c[i]]==0)nxt[0][0]=i;
        mp[c[i]]=i;
    }
    for(int i=0;i<=n;i++){
        if (nxt[i][0]==0)nxt[i][0]=n+1;
    }
    for(int i=n-1;i>=0;i--){
        nxt[i][0]=min(nxt[i][0],nxt[i+1][0]);
    }
    for(int i=1;i<=25;i++){
        for(int j=0;j<=n;j++){
            nxt[j][i]=nxt[nxt[j][i-1]][i-1];
        }
    }
    cin>>q;
    for(int query=1;query<=q;query++){
        cin>>l>>r;
        ll cur=l-1;
        ll res=0;
        for(int i=25;i>=0;i--){
            if (nxt[cur][i]<=r){
                res+=pw[i];
                cur=nxt[cur][i];
            }
        }
    }
}

Compilation message (stderr)

sumzero.cpp: In function 'int main()':
sumzero.cpp:13:20: warning: iteration 24 invokes undefined behavior [-Waggressive-loop-optimizations]
   13 |         nxt[n+1][i]=n+1;
      |         ~~~~~~~~~~~^~~~
sumzero.cpp:11:18: note: within this loop
   11 |     for(int i=1;i<=25;i++){
      |                 ~^~~~

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