Submission #1152245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152245		leo_pu	Sum Zero (RMI20_sumzero)	C++20	0 / 100	3 ms	1344 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;
#define OSN ios_base::sync_with_stdio(false); cin.tie(NULL);
#define fi first
#define se second
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define pll pair<long,long>
const int INF=1e9;
const int N=2e5+5;
const int MOD=1e9+7;
const int LOG=20;

int ar[N], en[N], val[N];
set<int> st;
set<pii> lis; // angka, idx
vector<pii> v;


int P[N][LOG];
int res[N][LOG];

int main() {
	OSN
	int n;
	cin >> n;

	for (int i=1 ; i<=n ; i++){
		cin >> ar[i];
	}
	st.insert(0);
	lis.insert({0,0});

	int cnt=0;
	for (int i=1,j=1 ; i<=n && j<=n  ; j++){
		// res++;
		// cout << i << ' ' << j << "\n";
		cnt+=ar[j];
		// cout << ar[j] << " INILHO\n";
		// cout << cnt << " inilah\n";
		// for (auto x : st) cout << x << ' ';
		// 	cout << '\n';
		// 	cout << st.count(cnt) << "\n";
		if (st.count(cnt)==1){
			for (auto x : lis){
				if (x.fi==cnt){
					// cout << "CEKKKKKK\n";
					// for (auto y : lis) cout << y.fi << ' ' << y.se << "\n";
					// cout << " ADA\n";
					en[x.se+1]=j;
					v.pb({i,x.se});
					break;
				}
			}
			i=j+1;
			cnt=0;
			st.clear();
			st.insert(0);
			lis.clear();
			lis.insert({0,j});
		}
		else {
			st.insert(cnt);
			lis.insert({cnt, j});
		}
			// cout << "\n";
	}

	// for (auto x : v) cout << x.fi <<' ' << x.se << '\n';
	// 	cout << "\n";

	int temp=n;
	for (int i=n ; i>0 ; i--){
		if (en[i]==0){
			val[i]=0;
			en[i]=temp;
		}
		else {
			val[i]=1;
			temp=i-1;
		}
	}


	// for (int i=1 ; i<=n ; i++){
	// 	cout << i << ' ' << en[i] << "\n";
	// }


	for (int i=0 ; i<LOG ; i++){
		P[n][i]=n;
		P[n+1][i]=n;
	}
	for (int i=n ; i>0 ; i--){
		P[i][0]=en[i];
		res[i][0]=val[i];
		for (int j=1 ; j<LOG ; j++){
			int x=P[i][j-1];
			P[i][j]=P[x+1][j-1];
			res[i][j]=res[i][j-1]+res[x+1][j-1];
		}
	}


	int q;
	cin >> q;

	while (q--){
		int a, b;
		cin >> a >> b;

		int ans=0;
		for (int i=LOG-1 ; i>=0 ; i--){
			if (P[a][i]<b){
				ans+=res[a][i];
				a=P[a][i]+1;
			}
		}
		if (en[a]<=b){
			ans+=val[a];
		}
		cout << ans << "\n";
	}
}

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