Submission #540976

#	Time	Username	Problem	Language	Result	Execution time	Memory
540976		l3nl3	Mountains (NOI20_mountains)	C++17	64 / 100	66 ms	17044 KiB

Mountains

/*#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")*/

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e5 + 7;

int n, b[N], p[N], t[N*4], ans;
pair<int, int> a[N];

void clr() {
	for (int i = 1; i < N*4; i++) {
		t[i] = 0;
	}
	return;
}

void build (int v, int tl, int tr) {
	if (tl == tr) {
		t[v] = 0;
		return;
	}
	int tm = (tl+tr) / 2;
	build(v+v, tl, tm);
	build(v+v+1, tm+1, tr);
	t[v] = t[v+v] + t[v+v+1];
}

void upd (int v, int tl, int tr, int p) {
	if (tl == tr) {
		t[v]++;
		return;
	}
	int tm = (tl+tr) / 2;
	if (p <= tm) upd(v+v, tl, tm, p);
	else upd(v+v+1, tm+1, tr, p);
	t[v] = t[v+v] + t[v+v+1];
}

int get (int v, int tl, int tr, int l, int r) {
	if (l <= tl && tr <= r) return t[v];
	if (tr < l || r < tl) return 0;
	int tm = (tl+tr) / 2;
	return get(v+v, tl, tm, l, r) + get(v+v+1, tm+1, tr, l, r);
}

signed main () {
 	//freopen("", "r", stdin);
 	//freopen("", "w", stdout);
 	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].first;
		a[i].second = i;
	}
	sort(a+1, a+n+1);
	int num = 0;
	a[0].first = -1;
	for (int i = 1; i <= n; i++) {
		if (a[i].first > a[i-1].first) num++;
		b[a[i].second] = num;
	}
	build(1, 1, n);
	for (int i = 1; i <= n; i++) {
		p[i] = get(1, 1, n, 1, b[i] - 1);
		upd(1, 1, n, b[i]);
	}     
	clr();
	reverse(b+1, b+n+1);
	build(1, 1,n);
	for (int i = 1; i <= n; i++) {
		int j = n-i+1;
		ans += p[j] * get(1, 1, n, 1, b[i]-1);
		upd(1, 1, n, b[i]);
	}	
	cout << ans;
}       

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