oj.uz

Submission #478189

# Submission time Handle Problem Language Result Execution time Memory
478189 2021-10-06T11:00:58 Z blue Mountains (NOI20_mountains) C++17
24 / 100
 146 ms 11660 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int maxN = 300'000;
int H[1+maxN];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    for(int i = 1; i <= N; i++) cin >> H[i];

    vector<int> ind(N);
    for(int i = 1; i <= N; i++) ind[i-1] = i;

    sort(ind.begin(), ind.end(), [] (int p, int q)
    {
        if(H[p] == H[q]) return p > q;
        return H[p] < H[q];
    });

    vector<long long> lft(1+N, 0), rgt(1+N, 0);

    vector<int> BIT(1+N, 0);
    for(int i: ind)
    {
        for(int j = i; j <= N; j += j&-j)
            BIT[j]++;

        for(int j = i-1; j >= 1; j -= j&-j)
            lft[i] += BIT[j];
    }
    // cerr << "check\n";

    BIT = vector<int>(1+N, 0);
    sort(ind.begin(), ind.end(), [] (int p, int q)
    {
        if(H[p] == H[q]) return p < q;
        return H[p] < H[q];
    });

    // cerr << "check\n";

    for(int i: ind)
    {
        for(int j = i; j <= N; j += j&-j)
            BIT[j]++;

        for(int j = N; j >= 1; j -= j&-j)
            rgt[i] += BIT[j];

        for(int j = i; j >= 1; j -= j&-j)
            rgt[i] -= BIT[j];
    }

    // for(int i = 1; i <= N; i++) cerr << lft[i] << ' ';
    // cerr << '\n';

    long long ans = 0;
    for(int i = 1; i <= N; i++) ans += lft[i] * rgt[i];

    cout << ans << '\n';
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 77 ms 8528 KB Output is correct
3 Correct 78 ms 8528 KB Output is correct
4 Correct 77 ms 8600 KB Output is correct
5 Correct 82 ms 8464 KB Output is correct
6 Correct 84 ms 8528 KB Output is correct
7 Correct 80 ms 8580 KB Output is correct
8 Correct 79 ms 8572 KB Output is correct
9 Correct 77 ms 8576 KB Output is correct
10 Correct 75 ms 8588 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 10188 KB Output is correct
2 Correct 113 ms 10184 KB Output is correct
3 Correct 93 ms 10284 KB Output is correct
4 Correct 114 ms 10184 KB Output is correct
5 Correct 93 ms 10220 KB Output is correct
6 Correct 105 ms 10168 KB Output is correct
7 Correct 105 ms 10184 KB Output is correct
8 Correct 119 ms 10312 KB Output is correct
9 Correct 120 ms 10172 KB Output is correct
10 Correct 0 ms 208 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 10188 KB Output is correct
2 Correct 113 ms 10184 KB Output is correct
3 Correct 93 ms 10284 KB Output is correct
4 Correct 114 ms 10184 KB Output is correct
5 Correct 93 ms 10220 KB Output is correct
6 Correct 105 ms 10168 KB Output is correct
7 Correct 105 ms 10184 KB Output is correct
8 Correct 119 ms 10312 KB Output is correct
9 Correct 120 ms 10172 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 117 ms 10548 KB Output is correct
12 Correct 118 ms 10552 KB Output is correct
13 Correct 115 ms 10440 KB Output is correct
14 Correct 112 ms 10552 KB Output is correct
15 Correct 128 ms 10548 KB Output is correct
16 Correct 119 ms 10440 KB Output is correct
17 Correct 113 ms 10436 KB Output is correct
18 Correct 86 ms 10508 KB Output is correct
19 Correct 81 ms 10440 KB Output is correct
20 Correct 1 ms 208 KB Output is correct

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 10188 KB Output is correct
2 Correct 113 ms 10184 KB Output is correct
3 Correct 93 ms 10284 KB Output is correct
4 Correct 114 ms 10184 KB Output is correct
5 Correct 93 ms 10220 KB Output is correct
6 Correct 105 ms 10168 KB Output is correct
7 Correct 105 ms 10184 KB Output is correct
8 Correct 119 ms 10312 KB Output is correct
9 Correct 120 ms 10172 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 117 ms 10548 KB Output is correct
12 Correct 118 ms 10552 KB Output is correct
13 Correct 115 ms 10440 KB Output is correct
14 Correct 112 ms 10552 KB Output is correct
15 Correct 128 ms 10548 KB Output is correct
16 Correct 119 ms 10440 KB Output is correct
17 Correct 113 ms 10436 KB Output is correct
18 Correct 86 ms 10508 KB Output is correct
19 Correct 81 ms 10440 KB Output is correct
20 Correct 1 ms 208 KB Output is correct
21 Correct 122 ms 11424 KB Output is correct
22 Correct 125 ms 11432 KB Output is correct
23 Correct 126 ms 11472 KB Output is correct
24 Correct 125 ms 11360 KB Output is correct
25 Correct 126 ms 11408 KB Output is correct
26 Correct 146 ms 11660 KB Output is correct
27 Correct 130 ms 11432 KB Output is correct
28 Correct 77 ms 11396 KB Output is correct
29 Correct 72 ms 11356 KB Output is correct
30 Correct 0 ms 208 KB Output is correct

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 77 ms 8528 KB Output is correct
3 Correct 78 ms 8528 KB Output is correct
4 Correct 77 ms 8600 KB Output is correct
5 Correct 82 ms 8464 KB Output is correct
6 Correct 84 ms 8528 KB Output is correct
7 Correct 80 ms 8580 KB Output is correct
8 Correct 79 ms 8572 KB Output is correct
9 Correct 77 ms 8576 KB Output is correct
10 Correct 75 ms 8588 KB Output is correct
11 Correct 94 ms 10188 KB Output is correct
12 Correct 113 ms 10184 KB Output is correct
13 Correct 93 ms 10284 KB Output is correct
14 Correct 114 ms 10184 KB Output is correct
15 Correct 93 ms 10220 KB Output is correct
16 Correct 105 ms 10168 KB Output is correct
17 Correct 105 ms 10184 KB Output is correct
18 Correct 119 ms 10312 KB Output is correct
19 Correct 120 ms 10172 KB Output is correct
20 Correct 0 ms 208 KB Output is correct
21 Correct 117 ms 10548 KB Output is correct
22 Correct 118 ms 10552 KB Output is correct
23 Correct 115 ms 10440 KB Output is correct
24 Correct 112 ms 10552 KB Output is correct
25 Correct 128 ms 10548 KB Output is correct
26 Correct 119 ms 10440 KB Output is correct
27 Correct 113 ms 10436 KB Output is correct
28 Correct 86 ms 10508 KB Output is correct
29 Correct 81 ms 10440 KB Output is correct
30 Correct 1 ms 208 KB Output is correct
31 Incorrect 1 ms 336 KB Output isn't correct
32 Halted 0 ms 0 KB -