5404 2023. 05. 12 16:57:19 szil Barátok cpp14 Elfogadva 100/100 174ms 31016 KiB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 200001;

int a[MAXN], tree[2*MAXN], n;
vector<int> extra[MAXN];

void upd(int u) {
    u += n;
    tree[u]++;
    for (u /= 2; u >= 1; u /= 2) {
        tree[u] = tree[2*u]+tree[2*u+1];
    }
}

int qry(int l, int r) {
    l += n; r += n;
    int res = 0;
    while (l <= r) {
        if (l % 2 == 1) res += tree[l++];
        if (r % 2 == 0) res += tree[r--];
        l /= 2; r /= 2;
    }
    return res;
}


int main()
{
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        int l = max(1, i-a[i]);
        extra[l].push_back(i);
    }

    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += qry(i, n);
        for (int j : extra[i]) {
            ans -= qry(j, n);
        }
        upd(min(n, i+a[i]));
    }
    cout << ans << "\n";
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 6ms 11180 KiB
2 Elfogadva 96ms 17496 KiB
subtask2 11/11
3 Elfogadva 96ms 17496 KiB
4 Elfogadva 6ms 11744 KiB
5 Elfogadva 9ms 12144 KiB
6 Elfogadva 8ms 12368 KiB
7 Elfogadva 8ms 12436 KiB
8 Elfogadva 8ms 12696 KiB
9 Elfogadva 8ms 12584 KiB
10 Elfogadva 8ms 12824 KiB
11 Elfogadva 8ms 12588 KiB
subtask3 12/12
12 Elfogadva 8ms 12588 KiB
13 Elfogadva 130ms 25056 KiB
14 Elfogadva 126ms 25224 KiB
15 Elfogadva 130ms 25188 KiB
16 Elfogadva 115ms 28644 KiB
17 Elfogadva 127ms 25464 KiB
18 Elfogadva 112ms 29812 KiB
19 Elfogadva 126ms 27028 KiB
subtask4 31/31
20 Elfogadva 126ms 27028 KiB
21 Elfogadva 118ms 25664 KiB
22 Elfogadva 131ms 25664 KiB
23 Elfogadva 111ms 29680 KiB
24 Elfogadva 128ms 26660 KiB
25 Elfogadva 158ms 23388 KiB
26 Elfogadva 167ms 24840 KiB
27 Elfogadva 145ms 20220 KiB
28 Elfogadva 166ms 26068 KiB
29 Elfogadva 136ms 17884 KiB
subtask5 46/46
30 Elfogadva 136ms 17884 KiB
31 Elfogadva 136ms 26468 KiB
32 Elfogadva 150ms 26396 KiB
33 Elfogadva 174ms 26364 KiB
34 Elfogadva 115ms 29124 KiB
35 Elfogadva 148ms 24632 KiB
36 Elfogadva 111ms 30808 KiB
37 Elfogadva 130ms 17368 KiB
38 Elfogadva 131ms 17660 KiB
39 Elfogadva 152ms 24112 KiB
40 Elfogadva 112ms 31016 KiB
41 Elfogadva 153ms 24048 KiB
42 Elfogadva 158ms 26848 KiB
43 Elfogadva 165ms 26264 KiB
44 Elfogadva 144ms 20916 KiB
45 Elfogadva 162ms 25644 KiB