Submission #1136181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136181		Thanhs	Sum Zero (RMI20_sumzero)	C++20	100 / 100	448 ms	22448 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 = 5;
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 n + 1;
	if(y % 4 == 0) return par[x][y / 4];
	if(y == 0) return e[x];
	return cal(cal(x, y - 1) + 1, y - 1);
}

vector<ll> sus1, sus2;
int b[N], mp[N];

void solve (){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		a[i] += a[i - 1];
	}
	for(int i = 0; i <= n; i++){
		sus1.push_back(a[i]);
	}
	sort(sus1.begin(), sus1.end());
	sus2.push_back(sus1[0]);
	for(int i = 1; i < sus1.size(); i++){
		if(sus1[i] != sus1[i - 1]){
			sus2.push_back(sus1[i]);
		}
	}
	for(int i = 0; i <= n; i++){
		b[i] = lower_bound(sus2.begin(), sus2.end(), a[i]) - sus2.begin() + 1;
	}

	e[n + 1] = inf;
	mp[b[n]] = n;
	for(int i = n; i >= 1; i--){
		int p = mp[b[i - 1]];
		if(p == 0) p = inf;
		e[i] = min(e[i + 1], p);
		mp[b[i - 1]] = i - 1;
	}
	for(int i = 1; i <= n; i++){
		if(e[i] == inf) e[i] = n + 1;
	}
	for(int i = n; i >= 1; i--){
		par[i][0] = e[i];
		for(int j = 4; j <= 18; j += 4){
			par[i][j / 4] = cal(cal(i, j - 1) + 1, j - 1);
		}
	}

	int q; cin >> q;
	while(q--){
		int l, r;
		cin >> l >> r;
		int ans = 0;
		for(int i = 18; i >= 0; i--){
			if(l == n + 1) continue;
			int cur = cal(l, i);
			if(cur == n + 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: 39 / 39