Submission #990225

#	Time	Username	Problem	Language	Result	Execution time	Memory
990225		duzinho039	Sum Zero (RMI20_sumzero)	C++14	61 / 100	514 ms	65536 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using ii = pair<int, int>;
using vii = vector<ii>;

vi c;
vii queries;
int n, q;

void read() {
	cin >> n;
	c.resize(n);
	for(int &x: c) cin >> x;

	cin >> q;
	queries.resize(q);
	for(auto &[l, r]: queries) cin >> l >> r;
}

void solve() {
	map<int, int> where;

	vvi anc(n, vi(20, -100));
	int currsum = 0;
	int prev = -100;
	for(int i = 0; i < n; ++i) {
		currsum += c[i];
		if(where.find(currsum) != where.end()) {
			prev = max(prev, where[currsum]);
		}

		if(currsum == 0) {
			prev = max(prev, -1);
		}

		anc[i][0] = prev;
		for(int b = 1; b < 20; ++b) {
			if(anc[i][b - 1] <= -1) {
				break;
			}

			anc[i][b] = anc[anc[i][b - 1]][b - 1];
		}

		where[currsum] = i;
	}


	for(auto [l, r]: queries) {
		l--;
		r--;

		int ans = 0;

		for(int b = 19; b >= 0; --b) {
			if(r == -1) break;
			int nr = anc[r][b];

			if(nr >= l - 1) {
				r = nr;
				ans |= 1 << b;
			}
		}

		cout << ans << '\n';
	}

}

int main() {
	read();
	solve();
}

Compilation message (stderr)

sumzero.cpp: In function 'void read()':
sumzero.cpp:21:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |  for(auto &[l, r]: queries) cin >> l >> r;
      |            ^
sumzero.cpp: In function 'void solve()':
sumzero.cpp:53:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |  for(auto [l, r]: queries) {
      |           ^

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