Submission #496683

#	Time	Username	Problem	Language	Result	Execution time	Memory
496683		Elias	Sum Zero (RMI20_sumzero)	C++17	61 / 100	796 ms	65536 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;

struct Range
{
	int s, e;
};

signed main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	int n;
	cin >> n;

	vector<int> v(n);

	int last = 0;
	for (int &i : v)
	{
		cin >> i;
		i = last += i;
	}

	vector<Range> ranges;

	map<int, int> brr;
	brr[0] = -1;

	for (int i = 0; i < n; i++)
	{
		auto x = brr.find(v[i]);
		if (x != brr.end())
			ranges.push_back(Range{(*x).second + 1, i});
		brr[v[i]] = i;
	}

	int j = 0;

	vector<vector<int>> jump(n + 2, vector<int>(25, n + 1));
	jump[n][0] = n + 1;

	for (int i = 0; i < n; i++)
	{

		while (ranges[j].s < i)
			if (++j >= ranges.size())
				goto exit;

		jump[i][0] = ranges[j].e + 1;
	}
exit:

	for (int j = 1; j < 25; j++)
		for (int i = 0; i < n; i++)
			jump[i][j] = jump[jump[i][j - 1]][j - 1];

	int q;
	cin >> q;

	while (q--)
	{
		int a, b;
		cin >> a >> b;

		a--;

		int num = 0;

		for (int j = 24; j >= 0; j--)
		{
			if (jump[a][j] <= b)
			{
				num += (1 << j);
				a = jump[a][j];
			}
		}
		cout << num << "\n";
	}
}

Compilation message (stderr)

sumzero.cpp: In function 'int main()':
sumzero.cpp:49:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Range>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |    if (++j >= ranges.size())
      |        ~~~~^~~~~~~~~~~~~~~~

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