Submission #1273779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273779		nguyenbaoanh	Sum Zero (RMI20_sumzero)	C++20	61 / 100	299 ms	47256 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=4e5, B=1024;
const ll Mod=1e9+7, oo=1e18;
int n, q, l, r, res=0, up[N+5][20];
ll a[N+5];
map<ll, int> 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], a[i]+=a[i-1];
    up[n+1][0]=n+1;
    for(int i=n; i>=0; i--) {
        if(mp[a[i]]) up[i][0]=mp[a[i]]; else up[i][0]=n+1;
        up[i][0]=min(up[i][0], up[i+1][0]);
        mp[a[i]]=i;
    }
    for(int j=1; j<20; j++)
        for(int i=0; i<=n+1; i++) up[i][j]=up[up[i][j-1]][j-1];
    cin>>q;
    while(q--) {
        cin>>l>>r;
        res=0;
        l--;
        for(int i=19; i>=0; i--)
            while(up[l][i]<=r) res+=(1<<i), l=up[l][i];
        cout<<res<<'\n';
    }
    return 0;
}

Compilation message (stderr)

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

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