Submission #563554

#	Time	Username	Problem	Language	Result	Execution time	Memory
563554		Cookie	Mountains (NOI20_mountains)	C++14	24 / 100	223 ms	20936 KiB

Mountains

#include <bits/stdc++.h>
using namespace std;
#define LIFESUCKS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ld long double
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define ar array
#include<cstdio>
#define vt vector
#include<fstream>
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define length(x) (int)(x).size()
#define fi first
#define se second
#define vt vector
int n;
int a[300000];
int b[300000];
vt<int>tree; vt<int>tr;
int gett(int nd, int l, int r, int q_l, int q_r){
	if(q_l > r || q_r < l)return(0);
	if(q_l <= l && q_r >= r)return(tree[nd]);
	int mid = (l + r) >> 1;
	return(gett((nd << 1), l, mid, q_l, q_r) + gett((nd << 1) + 1, mid + 1, r, q_l, q_r));
}
int get(int nd, int l, int r, int q_l, int q_r){
	if(q_l > r || q_r < l)return(0);
	if(q_l <= l && q_r >= r)return(tr[nd]);
	int mid = (l + r) >> 1;
	return(get((nd << 1), l, mid, q_l, q_r) + get((nd << 1) + 1, mid + 1, r, q_l, q_r));
}
void upd(int p){
	tree[p + n]++;
	for(int i = (p + n) >> 1; i >= 1; i = i >> 1){
		tree[i]++;
	}
}
void updd(int p, ll v){
	tr[p + n] += v;
	for(int i = (p + n) >> 1; i >= 1; i = i >> 1){
		tr[i] += v;
	}
}

int main(){
    LIFESUCKS;
    cin >> n;
    int cr = n;
    for(int i = 0; i < n; i++){
        cin >> a[i]; b[i] = a[i];
    }
    sort(b, b + n);
    for(int i = 0; i < n; i++){
        a[i] = lower_bound(b, b + n, a[i]) - b;
    }
	while(__builtin_popcount(n) != 1)n++;
	
	tree.resize(2 * n, 0);
	ll left[n] = {0};
	for(int i = cr - 1; i >= 0; i--){
	    left[i] = gett(1, 0, n - 1, 0, a[i] - 1);
	    upd(a[i]);
	}
	ll right[n] = {0};
	tr.resize(2 * n, 0);
	for(int i = 0; i < cr; i++ ){
	    right[i] = get(1, 0, n - 1, 0, a[i] - 1);
	    updd(a[i], 1);
	}
	ll ans = 0;
	for(int i = 1; i < n - 1; i++){
	    ans += (right[i] * left[i]);
	}
	cout << ans;
}

Compilation message (stderr)

Mountains.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("O3")
      | 
Mountains.cpp:8: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    8 | #pragma GCC optimization ("unroll-loops")
      |

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 0 / 36
• Subtask 5: 0 / 28
• Subtask 6: 9 / 9
• Subtask 7: 0 / 12