Submission #1267483

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267483		tle_god	Mountains (NOI20_mountains)	C++20	100 / 100	114 ms	12304 KiB

Mountains

/*
 *|---------------------------------------------|*
 *|       Author  : Le Hoang An                 |*
 *|     From  :  Bien Hoa Gifted High School    |*
 *|---------------------------------------------|*
 *|                ADOMINATION                  |*
 *|---------------------------------------------|*
*/
//#pragma GCC optimize("02,unroll-loops")
#include <bits/stdc++.h>
#define f0(i, n) for(int i=0; i<n; i++)
#define f1(i, n) for(int i=1; i<=n; i++)
#define fi first
#define se second
#define pb push_back
#define ep emplace_back
#define el cout << "\n";
#define sz(A) (int)A.size()
#define FOR(i, l, r) for (int i = l; i <= r; i++)
#define FOD(i, r, l) for (int i = r; i >= l; i--)
#define all(x) x.begin(), x.end()
#define faster                       \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                     \
    cout.tie(NULL);
#define Ado signed main()
using namespace std;
#define int long long
#define itn int
typedef long long ll;
typedef pair<int, int> ii;
typedef unsigned long long ull;
typedef string str;
typedef vector<int> vi;
const int maxn=1000002;
const int mod=1000000007;
const ll inf = 1e18;
#define bit(mask, i) ((mask>>i)&1)
#define lon(x) ((1ll) << (x))
template <class X, class Y>
    bool maximize(X &x, const Y&y)
    {
        if(x<y)
        {
            x=y;
            return true;
        }
        else return false;
    }
template <class X, class Y>
    bool minimize(X &x, const Y&y)
    {
        if(x>y)
        {
            x=y;
            return true;
        }
        else return false;
    }

void file()
{
      #define TASK "Himawari"
    if(fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }
}
struct Fenwick{
    vi bit;
    int N;
    Fenwick(int _n = 0){
        N = _n; bit.assign(N + 1, 0);
    }
    void update(int u, int val){
        for(; u <= N; u += u &-u) 
            bit[u] += val;
    }
    int get(int u){
        int res = 0;
        for(; u > 0; u -= u & -u)
            res += bit[u];
        return res;
    }
};
int n, a[maxn];
ll pre[maxn], ans = 0;
Ado
{
    faster;
    file();
    cin >> n;
    vi comp;
    FOR(i, 1, n){
        cin >> a[i];
        comp.pb(a[i]);
    }
    sort(all(comp));
    comp.erase(unique(all(comp)), comp.end());
    FOR(i, 1, n){
        a[i] = lower_bound(all(comp), a[i]) - comp.begin() + 1;
    }
    Fenwick fen(sz(comp) + 1);
    FOR(i, 1, n){
        pre[i] = fen.get(a[i] - 1);
        fen.update(a[i], 1);
    }
    fen = Fenwick(sz(comp) + 1);
    FOD(i, n, 1){
        ll suf = fen.get(a[i] - 1);
        ans += suf * pre[i];
        fen.update(a[i], 1);
    }

    cout << ans;
    return 0;
}

Compilation message (stderr)

Mountains.cpp: In function 'void file()':
Mountains.cpp:66:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Mountains.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen(TASK".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