Submission #645897

#	Time	Username	Problem	Language	Result	Execution time	Memory
645897		blue	Sum Zero (RMI20_sumzero)	C++17	22 / 100	1082 ms	3616 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using ll = long long;

ll* c;

int main()
{
	int N;
	cin >> N;

	ll d[N+1];
	c = d;
	c[0] = 0;
	for(int i = 1; i <= N; i++)
	{
		cin >> c[i];
		c[i] += c[i-1];
	}

	int lst[N+1];
	for(int i = 0; i <= N; i++)
		lst[i] = i;
	sort(lst, lst+N+1, [] (int u, int v)
	{
		if(c[u] == c[v])
			return u < v;
		return c[u] < c[v];
	});

	int nxt[N+1];
	for(int i = 0; i <= N; i++)
		nxt[i] = N+1;

	for(int i = 0; i+1 <= N; i++)
	{
		if(c[lst[i]] == c[lst[i+1]])
			nxt[lst[i]] = lst[i+1];
	}

	// for(int i = 0; i <= N; i++)
	// 	cerr << nxt[i] << ' ';
	// cerr << '\n';

	for(int i = N-1; i >= 0; i--)
		nxt[i] = min(nxt[i], nxt[i+1]);

	int Q;
	cin >> Q;

	// cerr << "done\n";

	for(int j = 1; j <= Q; j++)
	{
		int L, R;
		cin >> L >> R;
		L--;

		int res = 0;
		while(nxt[L] <= R)
		{
			L = nxt[L];
			res++;
		}

		cout << res << '\n';
	}
}

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