oj.uz

Submission #339794

# Submission time Handle Problem Language Result Execution time Memory
339794 2020-12-26T08:31:20 Z mihai145 Mountains (NOI20_mountains) C++14
24 / 100
 691 ms 11372 KB 
#include <iostream>
#include <set>
#include <map>

using namespace std;

const int NMAX = 3e5;

int N, v[NMAX + 5];
set <int> xs;

int k;
map <int, int> norm;

int st[NMAX + 5], dr[NMAX + 5];

struct AIB {
    int n, v[NMAX + 5];

    void Reset(int _n) {
        n = _n;
        for(int i = 0; i <= n; i++)
            v[i] = 0;
    }

    int Lsb(int x) {
        return x & (-x);
    }

    void Update(int pos, int val) {
        for(int i = pos; i <= n; i += Lsb(i))
            v[i] += val;
    }

    int Query(int pos) {
        int ans = 0;

        for(int i = pos; i > 0; i -= Lsb(i))
            ans += v[i];

        return ans;
    }
};

AIB aib;

int main()
{
    cin >> N;

    for(int i = 1; i <= N; i++) {
        cin >> v[i];
        xs.insert(v[i]);
    }

    while(!xs.empty()) {
        int val = *xs.begin();
        xs.erase(xs.begin());
        norm[val] = ++k;
    }

    aib.Reset(N);
    for(int i = 1; i <= N; i++) {
        st[i] = aib.Query(norm[v[i]] - 1);
        aib.Update(norm[v[i]], 1);
    }

    aib.Reset(N);
    for(int i = N; i >= 1; i--) {
        dr[i] = aib.Query(norm[v[i]] - 1);
        aib.Update(norm[v[i]], 1);
    }

    long long sol = 0;
    for(int i = 1; i <= N; i++)
        sol += 1LL * st[i] * dr[i];

    cout << sol << '\n';

    return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 34 ms 3820 KB Output is correct
3 Correct 36 ms 3820 KB Output is correct
4 Correct 34 ms 3820 KB Output is correct
5 Correct 36 ms 3840 KB Output is correct
6 Correct 34 ms 3820 KB Output is correct
7 Correct 34 ms 3820 KB Output is correct
8 Correct 42 ms 3820 KB Output is correct
9 Correct 34 ms 3820 KB Output is correct
10 Correct 34 ms 3820 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 5612 KB Output is correct
2 Correct 86 ms 5612 KB Output is correct
3 Correct 89 ms 5556 KB Output is correct
4 Correct 90 ms 5552 KB Output is correct
5 Correct 86 ms 5612 KB Output is correct
6 Correct 93 ms 5612 KB Output is correct
7 Correct 84 ms 5612 KB Output is correct
8 Correct 95 ms 5540 KB Output is correct
9 Correct 84 ms 5612 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 5612 KB Output is correct
2 Correct 86 ms 5612 KB Output is correct
3 Correct 89 ms 5556 KB Output is correct
4 Correct 90 ms 5552 KB Output is correct
5 Correct 86 ms 5612 KB Output is correct
6 Correct 93 ms 5612 KB Output is correct
7 Correct 84 ms 5612 KB Output is correct
8 Correct 95 ms 5540 KB Output is correct
9 Correct 84 ms 5612 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 133 ms 5924 KB Output is correct
12 Correct 133 ms 5872 KB Output is correct
13 Correct 139 ms 5868 KB Output is correct
14 Correct 133 ms 5868 KB Output is correct
15 Correct 134 ms 5868 KB Output is correct
16 Correct 148 ms 5972 KB Output is correct
17 Correct 132 ms 5868 KB Output is correct
18 Correct 102 ms 5868 KB Output is correct
19 Correct 98 ms 5868 KB Output is correct
20 Correct 1 ms 364 KB Output is correct

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 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 364 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 86 ms 5612 KB Output is correct
2 Correct 86 ms 5612 KB Output is correct
3 Correct 89 ms 5556 KB Output is correct
4 Correct 90 ms 5552 KB Output is correct
5 Correct 86 ms 5612 KB Output is correct
6 Correct 93 ms 5612 KB Output is correct
7 Correct 84 ms 5612 KB Output is correct
8 Correct 95 ms 5540 KB Output is correct
9 Correct 84 ms 5612 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 133 ms 5924 KB Output is correct
12 Correct 133 ms 5872 KB Output is correct
13 Correct 139 ms 5868 KB Output is correct
14 Correct 133 ms 5868 KB Output is correct
15 Correct 134 ms 5868 KB Output is correct
16 Correct 148 ms 5972 KB Output is correct
17 Correct 132 ms 5868 KB Output is correct
18 Correct 102 ms 5868 KB Output is correct
19 Correct 98 ms 5868 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 619 ms 11352 KB Output is correct
22 Correct 691 ms 11196 KB Output is correct
23 Correct 591 ms 11372 KB Output is correct
24 Correct 683 ms 11244 KB Output is correct
25 Correct 573 ms 11204 KB Output is correct
26 Correct 691 ms 11372 KB Output is correct
27 Correct 556 ms 11244 KB Output is correct
28 Correct 251 ms 11372 KB Output is correct
29 Correct 283 ms 11336 KB Output is correct
30 Correct 1 ms 364 KB Output is correct

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 34 ms 3820 KB Output is correct
3 Correct 36 ms 3820 KB Output is correct
4 Correct 34 ms 3820 KB Output is correct
5 Correct 36 ms 3840 KB Output is correct
6 Correct 34 ms 3820 KB Output is correct
7 Correct 34 ms 3820 KB Output is correct
8 Correct 42 ms 3820 KB Output is correct
9 Correct 34 ms 3820 KB Output is correct
10 Correct 34 ms 3820 KB Output is correct
11 Correct 86 ms 5612 KB Output is correct
12 Correct 86 ms 5612 KB Output is correct
13 Correct 89 ms 5556 KB Output is correct
14 Correct 90 ms 5552 KB Output is correct
15 Correct 86 ms 5612 KB Output is correct
16 Correct 93 ms 5612 KB Output is correct
17 Correct 84 ms 5612 KB Output is correct
18 Correct 95 ms 5540 KB Output is correct
19 Correct 84 ms 5612 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 133 ms 5924 KB Output is correct
22 Correct 133 ms 5872 KB Output is correct
23 Correct 139 ms 5868 KB Output is correct
24 Correct 133 ms 5868 KB Output is correct
25 Correct 134 ms 5868 KB Output is correct
26 Correct 148 ms 5972 KB Output is correct
27 Correct 132 ms 5868 KB Output is correct
28 Correct 102 ms 5868 KB Output is correct
29 Correct 98 ms 5868 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Incorrect 1 ms 364 KB Output isn't correct
32 Halted 0 ms 0 KB -