oj.uz

답안 #597360

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
597360 2022-07-16T00:00:59 Z pedroslrey Sum Zero (RMI20_sumzero) C++17
100 / 100
 214 ms 20452 KB 
#include <bits/stdc++.h>
 
using namespace std;
using lli = long long;
 
const int MAXN = 4e5 + 10;
const int MAXK = 20;
 
int ant[MAXN], dp[MAXN], prof[MAXN], ls[MAXN], rs[MAXN], ds[MAXN], tmp[MAXN];
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	int n;
	cin >> n;
 
	vector<pair<lli, int>> xs{{0, 0}};
	lli sum = 0;
	for (int i = 1; i <= n; ++i) {
		int x;
		cin >> x;
 
		sum += x;
		xs.emplace_back(sum, i);
	}
 
	vector<int> ant(n+1);
	for (int i = 1; i <= n; ++i)
		ant[i] = -1;
 
	sort(xs.begin(), xs.end());
	for (int i = 1; i <= n; ++i)
		if (xs[i].first == xs[i-1].first)
			ant[xs[i].second] = xs[i-1].second;
 
	dp[0] = -1;
 
	for (int i = 1; i <= n; ++i) {
		if (ant[i] < dp[i-1]) dp[i] = dp[i-1];
		else dp[i] = ant[i];

		prof[i] = 1 + (dp[i] == -1 ? -1 : prof[dp[i]]);
	}
 
	int q;
	cin >> q;
 
	for (int i = 0; i < q; ++i) {
		cin >> ls[i] >> rs[i];
		ds[i] = prof[rs[i]] - prof[ls[i]-1];	
	}

	for (int k = 0; k < MAXK; ++k) {
		for (int i = 0; i < q; ++i)
			if (ds[i] & (1 << k))
				rs[i] = dp[rs[i]];

		for (int i = 1; i <= n; ++i)
			if (dp[i] != -1) tmp[i] = dp[dp[i]];
			else tmp[i] = -1;

		for (int i = 1; i <= n; ++i)
			dp[i] = tmp[i];
	}

	for (int i = 0; i < q; ++i) {
		if (rs[i] < ls[i] - 1) cout << ds[i] - 1 << "\n";
		else cout << ds[i] << "\n";
	}
}

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 3 ms 596 KB Output is correct

Subtask #2
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 42 ms 5120 KB Output is correct
8 Correct 41 ms 4980 KB Output is correct
9 Correct 49 ms 5056 KB Output is correct
10 Correct 44 ms 5000 KB Output is correct
11 Correct 43 ms 4944 KB Output is correct
12 Correct 47 ms 5144 KB Output is correct

Subtask #3
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 42 ms 5120 KB Output is correct
8 Correct 41 ms 4980 KB Output is correct
9 Correct 49 ms 5056 KB Output is correct
10 Correct 44 ms 5000 KB Output is correct
11 Correct 43 ms 4944 KB Output is correct
12 Correct 47 ms 5144 KB Output is correct
13 Correct 179 ms 19512 KB Output is correct
14 Correct 212 ms 19932 KB Output is correct
15 Correct 214 ms 20440 KB Output is correct
16 Correct 205 ms 20352 KB Output is correct
17 Correct 184 ms 19888 KB Output is correct
18 Correct 208 ms 20452 KB Output is correct