Submission #1297575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297575		NotLinux	Sum Zero (RMI20_sumzero)	C++20	61 / 100	773 ms	45092 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
const int SQRT = 632;
void solve(){
    int n;
    cin >> n;
    int arr[n];
    for(int i = 0;i<n;i++)cin >> arr[i];
    long long pre[n+1];
	pre[0] = 0;
	for(int i = 0;i<n;i++){
		pre[i+1] = pre[i] + arr[i];
	}
	map<long long,int>mpa;
	int nxt[n+1];
	fill(nxt , nxt + n+1 , n+1);
	for(int i = n;i>=0;i--){
		if(mpa.count(pre[i])){
			nxt[i] = mpa[pre[i]];
		}
		mpa[pre[i]] = i;
	}
	vector<int>tree[n+2] , path;
	// cout << "flag0" << endl;
	int edge[n+1];
	memset(edge , -1 , sizeof(edge));
	for(int i = 0;i<=n;i++){
		edge[i] = nxt[i];
	}
	for(int i = n;i>=0;i--){
		if(i < n)
			edge[i] = min(edge[i] , edge[i+1]);
		tree[edge[i]].push_back(i);
	}
	// cout << "flag1" << endl;

	int jump1[n+1] , jump2[n+1];
	memset(jump1 , -1 , sizeof(jump1));
	memset(jump2 , -1 , sizeof(jump2));
	function<void(int)> dfs = [&](int node){
		if(!path.empty()){
			jump1[node] = path.back();
		}
		if(sz(path) - SQRT >= 0){
			jump2[node] = path[sz(path) - SQRT];
		}
		path.push_back(node);
		for(auto itr : tree[node]){
			dfs(itr);
		}
		path.pop_back();
	};
	dfs(n+1);
	int q;
	cin >> q;
	while(q--){
		int l,r;
		cin >> l >> r;
		l--;
		int ans = 0;
		while(l <= n and jump2[l] <= r and jump2[l] != -1){
			ans += SQRT;
			l = jump2[l];
		}
		while(l <= n and jump1[l] <= r and jump1[l] != -1){
			ans++;
			l = jump1[l];
		}
		cout << ans << '\n';
	}
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase=1;//cin >> testcase;
	while(testcase--)solve();
	cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}

Compilation message (stderr)

In file included from /usr/include/string.h:548,
                 from /usr/include/c++/13/cstring:42,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:121,
                 from sumzero.cpp:1:
In function 'void* memset(void*, int, size_t)',
    inlined from 'void solve()' at sumzero.cpp:28:8:
/usr/include/x86_64-linux-gnu/bits/string_fortified.h:59:33: warning: 'void* __builtin___memset_chk(void*, int, long unsigned int, long unsigned int)' specified bound between 18446744065119617028 and 18446744073709551612 exceeds maximum object size 9223372036854775807 [-Wstringop-overflow=]
   59 |   return __builtin___memset_chk (__dest, __ch, __len,
      |          ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
   60 |                                  __glibc_objsize0 (__dest));
      |                                  ~~~~~~~~~~~~~~~~~~~~~~~~~~

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