Submission #496644

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

sumzero

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

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

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

using namespace std;

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

vector<pair<int, int>> toRanges(vector<int> &vals) {
	map<int, int> already_used;
	vector<pair<int, int>> ranges;
	int actualSum = 0;
	vals.push_back(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()-1, vals.size()-2});
	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+1;
		}
	}
	for (int i = 1; i< path[0].size(); ++i) {
		for (int j = 0; j < path.size(); ++j) {
			path[j][i] = path[path[j][i-1]][i-1];
		}
	}
	return path;
}

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

signed main() {
	auto [vals, q] = input();
	auto ranges = toRanges(vals);
	vector<vector<int>> path = buildPath(ranges, vals.size());
	int l, r;
	for (int i = 0; i<q; ++i) {
		cin >> l >> r;
		cout << querryPath(path, l ,r) << "\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:29: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]
   29 |  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:44: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]
   44 |  for (auto [i, z] = make_pair(0,0); i < ranges.size() && z < path.size(); ++i) {
      |                                     ~~^~~~~~~~~~~~~~~
sumzero.cpp:44: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]
   44 |  for (auto [i, z] = make_pair(0,0); i < ranges.size() && z < path.size(); ++i) {
      |                                                          ~~^~~~~~~~~~~~~
sumzero.cpp:49: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]
   49 |  for (int i = 1; i< path[0].size(); ++i) {
      |                  ~^~~~~~~~~~~~~~~~
sumzero.cpp:50: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]
   50 |   for (int j = 0; j < path.size(); ++j) {
      |                   ~~^~~~~~~~~~~~~

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