Submission #1136166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136166		Thanhs	Sum Zero (RMI20_sumzero)	C++20	61 / 100	767 ms	24072 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;
#define name "aaaaaa"
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using ppii = pair<ll, pii>;
using pll = pair<ll, ll>;
using ull = unsigned long long;

void file(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	if(fopen(name".inp", "r")) {
		freopen(name".inp", "r", stdin);
		freopen(name".out", "w", stdout);
	}
}

const int N = 4e5 + 5;
const int L = 4;
const int inf = 1e9;

int n;
int a[N];
int par[N][L], dep[N];
int e[N];

int cal(int x, int y){
	if(x > n) return -1;
	if(y % 5 == 0) return par[x][y / 5];
	if(y == 0) return e[x];
	int c = cal(x, y - 1);
	if(c == -1) return -1;
	int res = cal(c + 1, y - 1);
	if(c + 1 == n + 1) res = -1;
	return res;
}

void solve (){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		a[i] += a[i - 1];
	}
	map<ll, int> mp;
	e[n + 1] = inf;
	mp[a[n]] = n;
	for(int i = n; i >= 1; i--){
		int p = mp[a[i - 1]];
		if(p == 0) p = inf;
		e[i] = min(e[i + 1], p);
		mp[a[i - 1]] = i - 1;
	}
	for(int i = 1; i <= n; i++){
		if(e[i] == inf) e[i] = -1;
	}
	for(int i = n; i >= 1; i--){
		par[i][0] = e[i];
		for(int j = 5; j <= 18; j += 5){
			if(cal(i, j - 1) == -1){
				par[i][j / 5] = -1;
				continue;
			}
			int p = cal(i, j - 1);
			par[i][j / 5] = cal(p + 1, j - 1);
			if(p + 1 == n + 1){
				par[i][j / 5] = -1;
			}
		}
	}

	int q; cin >> q;
	while(q--){
		int l, r;
		cin >> l >> r;
		int ans = 0;
		for(int i = 19; i >= 0; i--){
			if(l == n + 1) continue;
			int cur = cal(l, i);
			if(cur == -1 || cur > r || l == n + 1) continue;
			l = cur + 1;
			ans += (1 << i);
		}
		cout << ans << "\n";
	}
}

int main(){
	file();
	int test = 1;
	//cin >> test;
	while(test--){
		solve();
	}
}

Compilation message (stderr)

sumzero.cpp: In function 'void file()':
sumzero.cpp:14:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |                 freopen(name".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sumzero.cpp:15:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |                 freopen(name".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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