Submission #1164870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164870		emptypringlescan	Sum Zero (RMI20_sumzero)	C++20	61 / 100	174 ms	48840 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;
int par[400005];
int find(int x){
	if(par[x]==x) return x;
	return par[x]=find(par[x]);
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	for(int i=0; i<400005; i++) par[i]=i;
	int n;
	cin >> n;
	long long pref[n+1];
	unordered_map<long long,int> occ;
	occ[0]=0;
	pref[0]=0;
	int blk[n+1];
	memset(blk,-1,sizeof(blk));
	for(int i=1; i<=n; i++){
		cin >> pref[i];
		pref[i]+=pref[i-1];
		if(occ.find(pref[i])!=occ.end()){
			blk[i]=occ[pref[i]]+1;
		}
		occ[pref[i]]=i;
	}
	int q;
	cin >> q;
	pair<pair<int,int>,int> qu[q];
	for(int i=0; i<q; i++){
		cin >> qu[i].first.second >> qu[i].first.first;
		qu[i].second=i;
	}
	sort(qu,qu+q);
	int off[n+5],val[n+5],ans[q];
	memset(off,0,sizeof(off));
	memset(val,0,sizeof(val));
	vector<int> uwu[n+5];
	for(int i=1; i<=n; i++) uwu[i].push_back(i);
	int base=1,c=0;
	for(int i=1; i<=n; i++){
		if(blk[i]!=-1){
			for(; base<=blk[i]; base++){
				if(uwu[base].size()<=uwu[i+1].size()){
					for(int j:uwu[base]){
						uwu[i+1].push_back(j);
						val[j]+=off[base]-off[i+1]+1;
					}
					uwu[base].clear();
				}
				else{
					for(int j:uwu[i+1]){
						uwu[base].push_back(j);
						val[j]+=off[i+1]-off[base]-1;
					}
					uwu[i+1].clear();
					swap(uwu[base],uwu[i+1]);
					off[i+1]=off[base]+1;
					off[base]=0;
				}
				par[base]=i+1;
			}
		}
		while(c<q&&qu[c].first.first==i){
			ans[qu[c].second]=val[qu[c].first.second]+off[find(qu[c].first.second)];
			c++;
		}
	}
	for(int i=0; i<q; i++) cout << ans[i] << '\n';
}

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