Submission #1092892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092892		MrDogMeat	Mountains (NOI20_mountains)	C++17	100 / 100	125 ms	14328 KiB

Mountains

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

const int MAXN = 3e5 + 5;

struct BIT {
    int N, a[MAXN];

    void init(int _N) {
        N = _N;
        memset(a, 0, sizeof a);
    }

    void update(int p, int v) {
        for(; p <= N; p += p&-p) a[p] += v;
    }

    int get_sum(int p) {
        int s = 0;
        for(; p > 0; p -= p&-p) s += a[p];
        return s;
    }

    int get_sum(int l, int r) {
        return (get_sum(r) - get_sum(l - 1));
    }
};

///input
int N;
i64 H[MAXN];

///solution
int L[MAXN], R[MAXN];
BIT tree;

void solution() {
    cin >> N;
    vector<i64> zip;
    for(int i = 1; i <= N; i++)
    {
        cin >> H[i];
        zip.push_back(H[i]);
    }

    sort(zip.begin(), zip.end());
    zip.erase(unique(zip.begin(), zip.end()), zip.end());
    for(int i = 1; i <= N; i++)
    {
        H[i] = lower_bound(zip.begin(), zip.end(), H[i]) - zip.begin() + 1;
    }

    tree.init(N);
    for(int i = 1; i <= N; i++)
    {
        L[i] = tree.get_sum(1, H[i] - 1);
        tree.update(H[i], 1);
    }
    tree.init(N);
    for(int i = N; i > 0; i--)
    {
        R[i] = tree.get_sum(1, H[i] - 1);
        tree.update(H[i], 1);
    }

    i64 Ans = 0;
    for(int i = 1; i <= N; i++)
    {
        Ans += 1LL*L[i]*R[i];
    }

    cout << Ans;
}

#define FILE "C"
int main() {
    if(fopen(FILE".inp","r")) {
        freopen(FILE".inp","r",stdin);
        freopen(FILE".out","w",stdout);
    }
    cin.tie(nullptr) -> ios_base::sync_with_stdio(false);

    solution();

    return 0;
}

Compilation message (stderr)

Mountains.cpp: In function 'int main()':
Mountains.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         freopen(FILE".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Mountains.cpp:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         freopen(FILE".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• 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