Submission #1242033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242033		hynmj	Sum Zero (RMI20_sumzero)	C++20	61 / 100	283 ms	46864 KiB

sumzero

//~~~~~~~~~~~~~MJ®™~~~~~~~~~~~~~
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#define rep1(n) for(ll i=0; i<(ll)(n); ++i)
#define rep2(i,n) for(ll i=0; i<(ll)(n); ++i)
#define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i)
#define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c))
#define cut4(a,b,c,d,e,...) e
#define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define per1(n) for(ll i=((ll)n)-1; i>=0; --i)
#define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i)
#define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i)
#define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c))
#define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
#define ll long long
#define ln cout<<endl
// #define int long long
#define Code ios_base::sync_with_stdio(0);
#define by cin.tie(NULL);
#define Hayan cout.tie(NULL);
#define append push_back
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
#define vi vector<int>
#define ret(x) {cout<<x;return;}
#define ui map<int,int>
#define pi pair<int,int>
#define ff first
#define ss second
using namespace std;
template <typename T> using v = vector<T>;
const  int MOD = 1e9+7, N = 4e5+7;
int st[N][19];
long long pref[N];
void solve()
{
	long long n, q, e;
	cin >> n;
	vi a(n);
	rep(n)
	{
		cin >> e;
		a[i] = e;
	}

	rep(i, 1, n+1)
		pref[i] = pref[i-1] + a[i-1];
    rep(n+2) st[i][0] = n+1;

    map<long long, long long> last;
    
    per(i, n+1)
    {
        st[i][0] = (last.count(pref[i]) ? last[pref[i]] : n+1);
        last[pref[i]] = i;
    }

	per(i, n+1)
		st[i][0] = min(st[i][0], st[i+1][0]);

	rep(p, 1, 19)
	{
		rep(i, 0, n+2)
		{
			st[i][p] = st[st[i][p-1]][p-1];
		}
	}

	cin >> q;
	rep(q)
	{
		int  l, r, ans = 0;
		cin >> l >> r;
		l--;

		for (int i = 18; i >= 0; i--)
		{
			if (st[l][i] <= r)
			{
				l = st[l][i];
				ans += (1LL << i);
			}
		}
		cout << ans << " ";
	}
}

signed main()
{
	Code by Hayan
	int ans = 1;
	rep(ans)
	{
		solve(); ln;
	}
}

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