oj.uz

Submission #880706

# Submission time Handle Problem Language Result Execution time Memory
880706 2023-11-29T22:15:51 Z Acanikolic Sum Zero (RMI20_sumzero) C++14
0 / 100
 4 ms 5036 KB 
#include <bits/stdc++.h>
#define int long long

#define pb push_back

#define F first

#define S second

using namespace std;

const int N = 1e6 + 10;

const int inf = 1e18;

const int lg = 20;

int a[N],st[N][lg];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	map<int,vector<int>>last;
	int S = 0;
	for(int i = 1; i <= n; i++) {
		S += a[i];
		last[S].pb(i);
	}
	// pref[i] - pref[j-1] == 0
	// 
	int sum = 0;
	for(int i = 1; i <= n; i++) {
		int index = sum;
		sum += a[i];
		if(last[index].empty()) {
			st[i][0] = n + 1;
			continue;
		}
		int l = 0,r = last[index].size() - 1,ans = -1;
		while(l <= r) {
			int mid = (l + r) / 2;
			if(last[index][mid] >= i) {
				ans = mid;
				r = mid - 1;
			}else {
				l = mid + 1;
			}
		}
		if(ans == -1) st[i][0] = n + 1;
		else st[i][0] = last[index][ans];
	}
	for(int i = n - 1; i >= 1; i--) st[i][0] = min(st[i][0],st[i+1][0]);
	for(int j = 1; j < lg; j++) {
		for(int i = 1; i <= n; i++) {
			st[i][j] = st[min(st[i][j-1]+1,n)][j-1];
		}
	}
/*	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < lg; j++) cout << st[i][j] << ' ';
		cout << endl;
	}*/
	int q;
	cin >> q;
	while(q--) {
		int l,r,res = 0;
		cin >> l >> r;
		for(int j = lg - 1; j >= 0; j--) {
			if(st[l][j] <= r && st[l][j] != 0) {
				res += (1 << j);
				l = st[l][j] + 1;
				//cout << l << ' ' << st[l][0] << endl;
			}
		}
		cout << res << '\n';
	}
    return 0;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4956 KB Output is correct
2 Correct 4 ms 4956 KB Output is correct
3 Incorrect 4 ms 5036 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4956 KB Output is correct
2 Correct 4 ms 4956 KB Output is correct
3 Incorrect 4 ms 5036 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4956 KB Output is correct
2 Correct 4 ms 4956 KB Output is correct
3 Incorrect 4 ms 5036 KB Output isn't correct
4 Halted 0 ms 0 KB -