oj.uz

Submission #516445

# Submission time Handle Problem Language Result Execution time Memory
516445 2022-01-21T10:31:06 Z Jomnoi Mountains (NOI20_mountains) C++17
6 / 100
 318 ms 36844 KB 
#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;

const int MX = 3e5 + 10;

long long h[MX];

class Fenwick {
    protected :
        int N;
        vector <int> fenwick;
    public :
        Fenwick(const int &n) : N(n) {
            fenwick.resize(N, 0);
        }

        int lsb(const int &x) const {
            return x & -x;
        }

        void update(const int &i, const int &val) {
            for(int idx = i; idx <= N; idx += lsb(idx)) {
                fenwick[idx] += val;
            }
        }

        int query(const int &i) const {
            int res = 0;
            for(int idx = i; idx > 0; idx -= lsb(idx)) {
                res += fenwick[i];
            }
            return res;
        }
};

int main() {
    int n;
    scanf(" %d", &n);

    set <long long> s;
    unordered_map <long long, int> mp;
    for(int i = 1; i <= n; i++) {
        scanf(" %lld", &h[i]);
        s.insert(h[i]);
    }

    int cnt = 0;
    for(auto v : s) {
        mp[v] = ++cnt;
    }

    Fenwick fw1(cnt), fw2(cnt);
    for(int i = 2; i <= n; i++) {
        fw2.update(mp[h[i]], 1);
    }

    fw1.update(mp[h[1]], 1);
    long long ans = 0;
    for(int i = 2; i < n; i++) {
        fw2.update(mp[h[i]], -1);
        ans += 1ll * fw1.query(mp[h[i]] - 1) * fw2.query(mp[h[i]] - 1);
        fw1.update(mp[h[i]], 1);
    }
    cout << ans;
    return 0;
}

Compilation message

Mountains.cpp: In function 'int main()':
Mountains.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf(" %d", &n);
      |     ~~~~~^~~~~~~~~~~
Mountains.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf(" %lld", &h[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 300 KB Output is correct
2 Correct 310 ms 36728 KB Output is correct
3 Correct 308 ms 36720 KB Output is correct
4 Correct 318 ms 36844 KB Output is correct
5 Correct 306 ms 36760 KB Output is correct
6 Correct 292 ms 36676 KB Output is correct
7 Correct 310 ms 36752 KB Output is correct
8 Correct 295 ms 36688 KB Output is correct
9 Correct 161 ms 22828 KB Output is correct
10 Correct 173 ms 22952 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 3212 KB Output is correct
2 Correct 44 ms 3212 KB Output is correct
3 Correct 43 ms 3192 KB Output is correct
4 Correct 43 ms 3212 KB Output is correct
5 Correct 43 ms 3212 KB Output is correct
6 Correct 43 ms 3208 KB Output is correct
7 Correct 43 ms 3132 KB Output is correct
8 Correct 40 ms 3256 KB Output is correct
9 Correct 47 ms 3200 KB Output is correct
10 Correct 0 ms 204 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 3212 KB Output is correct
2 Correct 44 ms 3212 KB Output is correct
3 Correct 43 ms 3192 KB Output is correct
4 Correct 43 ms 3212 KB Output is correct
5 Correct 43 ms 3212 KB Output is correct
6 Correct 43 ms 3208 KB Output is correct
7 Correct 43 ms 3132 KB Output is correct
8 Correct 40 ms 3256 KB Output is correct
9 Correct 47 ms 3200 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Incorrect 56 ms 3436 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 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 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 3212 KB Output is correct
2 Correct 44 ms 3212 KB Output is correct
3 Correct 43 ms 3192 KB Output is correct
4 Correct 43 ms 3212 KB Output is correct
5 Correct 43 ms 3212 KB Output is correct
6 Correct 43 ms 3208 KB Output is correct
7 Correct 43 ms 3132 KB Output is correct
8 Correct 40 ms 3256 KB Output is correct
9 Correct 47 ms 3200 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Incorrect 56 ms 3436 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 300 KB Output is correct
2 Correct 310 ms 36728 KB Output is correct
3 Correct 308 ms 36720 KB Output is correct
4 Correct 318 ms 36844 KB Output is correct
5 Correct 306 ms 36760 KB Output is correct
6 Correct 292 ms 36676 KB Output is correct
7 Correct 310 ms 36752 KB Output is correct
8 Correct 295 ms 36688 KB Output is correct
9 Correct 161 ms 22828 KB Output is correct
10 Correct 173 ms 22952 KB Output is correct
11 Correct 43 ms 3212 KB Output is correct
12 Correct 44 ms 3212 KB Output is correct
13 Correct 43 ms 3192 KB Output is correct
14 Correct 43 ms 3212 KB Output is correct
15 Correct 43 ms 3212 KB Output is correct
16 Correct 43 ms 3208 KB Output is correct
17 Correct 43 ms 3132 KB Output is correct
18 Correct 40 ms 3256 KB Output is correct
19 Correct 47 ms 3200 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Incorrect 56 ms 3436 KB Output isn't correct
22 Halted 0 ms 0 KB -