oj.uz

Submission #516446

# Submission time Handle Problem Language Result Execution time Memory
516446 2022-01-21T10:32:25 Z Jomnoi Mountains (NOI20_mountains) C++17
6 / 100
 336 ms 31456 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 + 10, 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 204 KB Output is correct
2 Correct 323 ms 31456 KB Output is correct
3 Correct 311 ms 31344 KB Output is correct
4 Correct 311 ms 31212 KB Output is correct
5 Correct 317 ms 31340 KB Output is correct
6 Correct 293 ms 31340 KB Output is correct
7 Correct 309 ms 31412 KB Output is correct
8 Correct 336 ms 31352 KB Output is correct
9 Correct 158 ms 17484 KB Output is correct
10 Correct 181 ms 17444 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 2752 KB Output is correct
2 Correct 44 ms 2748 KB Output is correct
3 Correct 44 ms 2708 KB Output is correct
4 Correct 47 ms 2764 KB Output is correct
5 Correct 43 ms 2712 KB Output is correct
6 Correct 47 ms 2716 KB Output is correct
7 Correct 43 ms 2704 KB Output is correct
8 Correct 43 ms 2656 KB Output is correct
9 Correct 37 ms 2720 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 44 ms 2752 KB Output is correct
2 Correct 44 ms 2748 KB Output is correct
3 Correct 44 ms 2708 KB Output is correct
4 Correct 47 ms 2764 KB Output is correct
5 Correct 43 ms 2712 KB Output is correct
6 Correct 47 ms 2716 KB Output is correct
7 Correct 43 ms 2704 KB Output is correct
8 Correct 43 ms 2656 KB Output is correct
9 Correct 37 ms 2720 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Incorrect 54 ms 2760 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 44 ms 2752 KB Output is correct
2 Correct 44 ms 2748 KB Output is correct
3 Correct 44 ms 2708 KB Output is correct
4 Correct 47 ms 2764 KB Output is correct
5 Correct 43 ms 2712 KB Output is correct
6 Correct 47 ms 2716 KB Output is correct
7 Correct 43 ms 2704 KB Output is correct
8 Correct 43 ms 2656 KB Output is correct
9 Correct 37 ms 2720 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Incorrect 54 ms 2760 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 204 KB Output is correct
2 Correct 323 ms 31456 KB Output is correct
3 Correct 311 ms 31344 KB Output is correct
4 Correct 311 ms 31212 KB Output is correct
5 Correct 317 ms 31340 KB Output is correct
6 Correct 293 ms 31340 KB Output is correct
7 Correct 309 ms 31412 KB Output is correct
8 Correct 336 ms 31352 KB Output is correct
9 Correct 158 ms 17484 KB Output is correct
10 Correct 181 ms 17444 KB Output is correct
11 Correct 44 ms 2752 KB Output is correct
12 Correct 44 ms 2748 KB Output is correct
13 Correct 44 ms 2708 KB Output is correct
14 Correct 47 ms 2764 KB Output is correct
15 Correct 43 ms 2712 KB Output is correct
16 Correct 47 ms 2716 KB Output is correct
17 Correct 43 ms 2704 KB Output is correct
18 Correct 43 ms 2656 KB Output is correct
19 Correct 37 ms 2720 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Incorrect 54 ms 2760 KB Output isn't correct
22 Halted 0 ms 0 KB -