Submission #497698

#	Time	Username	Problem	Language	Result	Execution time	Memory
497698		42kangaroo	Sum Zero (RMI20_sumzero)	C++17	0 / 100	11 ms	1060 KiB

sumzero

//
// Created by 42kangaroo on 21/12/2021.
//

#include "vector"
#include "iostream"
#include "map"

#define log2(x) (8*sizeof(x) - __builtin_clzll(x))
#define int long long

using namespace std;

pair<vector<int>, int> input(){
	int n,q;
	cin >> n;
	vector<int> vals(n);
	for (int i = 0; i<n; ++i) {
		cin >> vals[i];
	}
	cin >> q;
	return {vals, q};
}

vector<pair<int, int>> toRanges(vector<int> &vals) {
	map<int, int> already_used;
	vector<pair<int, int>> ranges;
	int actualSum = 0;
	already_used.insert({0,0});
	for (int i = 0; i < vals.size(); ++i) {
		auto last_same_num = already_used.find(actualSum + vals[i]);
		if (last_same_num != already_used.end()) {
			ranges.push_back({last_same_num->second, i});
			last_same_num->second = i + 1;
		}
		already_used.insert({actualSum, i});
		actualSum += vals[i];
	}
	ranges.push_back({vals.size(), vals.size()});
	return ranges;
}

vector<vector<int>> buildPath(vector<pair<int, int>> &ranges, int size) {
	vector<vector<int>> path(size, vector<int>(log2(size)));
	for (auto [i, z] = make_pair(0,0); i < ranges.size() && z < path.size(); ++i) {
		for (; z<=ranges[i].first; ++z) {
			path[z][0] = ranges[i].second;
		}
	}
	for (int i = 1; i< path[0].size(); ++i) {
		for (int j = 0; j < path.size(); ++j) {
			if (path[j][i-1]==size-1) {
				path[j][i] = path[j][i-1];
				continue;
			}
			path[j][i] = path[path[j][i-1] +1][i-1];
		}
	}
	return path;
}

int querryPath(vector<vector<int>> &path, int l, int r) {
	int k = 1 << (path[0].size()-1);
	int num=0;
	int lastDest = l;
	while(k > 0) {
		if (path[lastDest][log2(k)-1]<=r) {
			num += k;
			lastDest = path[lastDest][log2(k)-1] + 1;
		}
		k >>= 1;
	}
	return num;
}

signed main() {
	auto [vals, q] = input();
	auto ranges = toRanges(vals);
	vector<vector<int>> path = buildPath(ranges, vals.size()+1);
	int l, r;
	for (int i = 0; i<q; ++i) {
		cin >> l >> r;
		cout << querryPath(path, l-1 ,r-1) << "\n";
	}
}

Compilation message (stderr)

sumzero.cpp: In function 'std::vector<std::pair<long long int, long long int> > toRanges(std::vector<long long int>&)':
sumzero.cpp:30:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for (int i = 0; i < vals.size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
sumzero.cpp: In function 'std::vector<std::vector<long long int> > buildPath(std::vector<std::pair<long long int, long long int> >&, long long int)':
sumzero.cpp:45:39: warning: comparison of integer expressions of different signedness: 'std::tuple_element<0, std::pair<int, int> >::type' {aka 'int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for (auto [i, z] = make_pair(0,0); i < ranges.size() && z < path.size(); ++i) {
      |                                     ~~^~~~~~~~~~~~~~~
sumzero.cpp:45:60: warning: comparison of integer expressions of different signedness: 'std::tuple_element<1, std::pair<int, int> >::type' {aka 'int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for (auto [i, z] = make_pair(0,0); i < ranges.size() && z < path.size(); ++i) {
      |                                                          ~~^~~~~~~~~~~~~
sumzero.cpp:50:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for (int i = 1; i< path[0].size(); ++i) {
      |                  ~^~~~~~~~~~~~~~~~
sumzero.cpp:51:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for (int j = 0; j < path.size(); ++j) {
      |                   ~~^~~~~~~~~~~~~

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