Submission #516448

#	Time	Username	Problem	Language	Result	Execution time	Memory
516448		Jomnoi	Mountains (NOI20_mountains)	C++17	100 / 100	548 ms	36828 KiB

Mountains

#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[idx];
            }
            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);
    }
    printf("%lld", ans);
    return 0;
}

Compilation message (stderr)

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 / 2
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 36 / 36
• Subtask 5: 28 / 28
• Subtask 6: 9 / 9
• Subtask 7: 12 / 12