Submission #1273723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273723		nguyenbaoanh	Sum Zero (RMI20_sumzero)	C++20	0 / 100	3 ms	2104 KiB

sumzero

//Author: NguyenBaoAnh
//Problem: EXCHANGE
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define vi vector<int>
#define pb push_back
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define fi first
#define se second
const int N=2e5, B=1024;
const ll Mod=1e9+7, oo=1e18;
int n, q;
ii up[N+5][20];
ll a[N+5], pre[N+5];
map<ll, ll> mp;
main()
{
    //Nothing beats a Jet-2 Holiday!
    //And right now, you can save 50 pounds per person.
    //That's 200 pounds for a family of 4!
    //freopen("runaway.in", "r", stdin); freopen("runaway.out", "w", stdout);
    ios_base::sync_with_stdio(NULL), cin.tie(NULL), cout.tie(NULL);
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i], pre[i]=pre[i-1]+a[i];
    for(int i=n; i>0; i--) {
        mp[pre[i]]=i;
        if(mp.count(pre[i-1])) up[i][0]={mp[pre[i-1]]+1, 1};
        else up[i][0]={i+1, 0};
    }
    up[n+1][0]={n+2, 0};
    up[n+2][0]={n+2, 0};
    for(int j=1; j<20; j++)
        for(int i=1; i<=n+2; i++) {
            ii t=up[i][j-1];
            up[i][j].fi=up[t.fi][j-1].fi;
            up[i][j].se=t.se+up[t.fi][j-1].se;
        }
    cin>>q;
    while(q--) {
        int l, r; cin>>l>>r;
        int res=0;
        for(int i=19; i>=0; i--)
            while(up[l][i].fi-1<=r && l<=r)
                //cout<<i<<' '<<l<<' '<<up[l][i].fi<<'\n',
                res+=up[l][i].se, l=up[l][i].fi;
        cout<<res<<'\n';
    }
    return 0;
}

Compilation message (stderr)

sumzero.cpp:19:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   19 | main()
      | ^~~~

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