Submission #1241985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241985		ghammazhassan	Sum Zero (RMI20_sumzero)	C++20	0 / 100	11 ms	14460 KiB

sumzero

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
using namespace std;
// #define int long long
#define endl "\n"
#define fi first
#define se second
const int M=998244353;
// const int inf = 3e9;
const int LOG=10;
const int N=4e5+5;
int n , m , c , w , k , t=1 , q=1 , x , y , z , l , r;
// vector<int>a[N];
int p[LOG][N];
// int mx[LOG][N];
map<int,int>d;
void makest(){
	for (int j=1;j<LOG;j++){
		for (int i=1;i<N;i++){
			p[j][i]=p[j-1][p[j-1][p[j-1][p[j-1][i]]]];
		}
	}
}
// void makest2(){
// 	for (int j=1;j<LOG;j++){
// 		for (int i=1;i<N-(1<<(j));i++){
// 			mx[j][i]=max(mx[j-1][i],mx[j-1][i+(1<<(j-1))]);
// 		}
// 	}
// }
// int mxt(int l,int r){
// 	int d=r-l+1;
// 	int c=0;
// 	while (d>1){
// 		d/=2;
// 		c++;
// 	}
// 	return max(mx[c][l],mx[c][r-(1<<c)+1]);
// }
// int bl(int x,int d){
// 	int k=LOG-1;
// 	while (k>=0){
// 		if (d>=(1<<k)){
// 			x=p[k][x];
// 			d-=(1<<k);
// 		}
// 		k--;
// 	}
// 	return x;
// }
// int lca(int x,int y){
// 	if (dep[x]<dep[y]){
// 		swap(x,y);
// 	}
// 	x=bl(x,dep[x]-dep[y]);
// 	if (x==y){
// 		return x;
// 	}
// 	int k=LOG-1;
// 	while (k>=0){
// 		if (p[k][x]!=p[k][y]){
// 			x=p[k][x];
// 			y=p[k][y];
// 		}
// 		k--;
// 	}
// 	return p[0][x];
// }
void solve()
{	
	cin >> n;
	vector<int>a(n+1);

	for (int i=1;i<=n;i++){
		cin >> a[i];
		x+=a[i];
		p[0][i]=d[x];
		
		d[x]=i;
		p[0][i]=max(p[0][i],p[0][i-1]);
		// cout << p[0][i] << " ";
	}
	// cout << endl;
	makest();
	cin >> q;
	for (int i=0;i<q;i++){
		cin >> l >> r;
		int k=LOG-1;
		int d=0;
		while (k>=0){
			while(p[k][r]>=l){
				d+=(1<<k);
				r=p[k][r];
			}
			k--;
		}
		if (p[0][r]==l-1)d++;
		cout << d << endl;
	}

	// queue<int>o;
	// o.push(1);
	// while (!o.empty()){
	// 	int h=o.front();
	// 	o.pop();
	// 	for (int i:a[h]){
	// 		if (dep[i])continue;
	// 		dep[i]=dep[h]+1;
	// 		o.push(i);
	// 	}
	// }
	


}
signed main()	
{

	ios::sync_with_stdio(0);//DO NOT USE IN INTERACTIVE
	cin.tie(0), cout.tie(0);//DO NOT USE IN INTERACTIVE
	cout << fixed<<setprecision(9);
	srand(time(0));
	// int t=1;
	// cin >> t;
	for (int _=1;_<=t;_++){
		solve();
		q++;
	}
}  

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