5431 2023. 05. 25 18:44:15 111 Barátok cpp14 Accepted 100/100 344ms 58176 KiB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
	int N;
	cin >> N;
	vector<int> v(N + 1);
	vector<vector<int>> u(N + 1);
	vector<vector<int>> w(N + 1);
	for (int i = 1; i <= N; i++) {
		cin >> v[i];
		u[max(1, i - v[i])].push_back(i);
		w[min(N, i)].push_back(i);
	}
	ordered_set<int> s;
	long long x = 0;
	for (int i = 1; i <= N; i++) {
		for (int j : u[i]) {
			s.insert(j);
		}
		x += s.order_of_key(min(N + 1, i + v[i] + 1)) - s.order_of_key(max(1, i - v[i])) - 1;
		for (int j : w[i]) {
			s.erase(j);
		}
	}
	cout << x << endl;
	return 0;
}
Subtask Sum Test Verdict Time Memory
subtask1 0/0
1 Accepted 3ms 1872 KiB
2 Accepted 189ms 31456 KiB
subtask2 11/11
3 Accepted 189ms 31456 KiB
4 Accepted 3ms 2336 KiB
5 Accepted 7ms 3472 KiB
6 Accepted 7ms 3724 KiB
7 Accepted 7ms 3996 KiB
8 Accepted 7ms 4004 KiB
9 Accepted 7ms 4340 KiB
10 Accepted 4ms 4072 KiB
11 Accepted 7ms 4216 KiB
subtask3 12/12
12 Accepted 7ms 4216 KiB
13 Accepted 164ms 43812 KiB
14 Accepted 151ms 44016 KiB
15 Accepted 162ms 43960 KiB
16 Accepted 97ms 47396 KiB
17 Accepted 158ms 44328 KiB
18 Accepted 87ms 48844 KiB
19 Accepted 142ms 46088 KiB
subtask4 31/31
20 Accepted 142ms 46088 KiB
21 Accepted 137ms 44408 KiB
22 Accepted 149ms 44456 KiB
23 Accepted 90ms 48472 KiB
24 Accepted 136ms 45328 KiB
25 Accepted 344ms 51564 KiB
26 Accepted 333ms 48256 KiB
27 Accepted 317ms 54488 KiB
28 Accepted 275ms 45888 KiB
29 Accepted 293ms 56692 KiB
subtask5 46/46
30 Accepted 293ms 56692 KiB
31 Accepted 174ms 45116 KiB
32 Accepted 211ms 45700 KiB
33 Accepted 263ms 46296 KiB
34 Accepted 123ms 48372 KiB
35 Accepted 256ms 47880 KiB
36 Accepted 104ms 49836 KiB
37 Accepted 277ms 57980 KiB
38 Accepted 289ms 58176 KiB
39 Accepted 337ms 52832 KiB
40 Accepted 105ms 50256 KiB
41 Accepted 324ms 52484 KiB
42 Accepted 282ms 46468 KiB
43 Accepted 293ms 47652 KiB
44 Accepted 310ms 55444 KiB
45 Accepted 310ms 49280 KiB