Submission #343393

#	Time	Username	Problem	Language	Result	Execution time	Memory
343393		zapan4	Mountains (NOI20_mountains)	C++17	100 / 100	694 ms	36632 KiB

Mountains

#include <iostream>
#include <cmath> 
#include <stdio.h>
#include <array>
#include <vector>
#include <list>
#include <algorithm>
#include <utility>
#include <string>
#include <sstream>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#define pp pair<int,int>
#define pll pair<ll, ll>
#define ll long long
using namespace std;

map<ll, ll> normalizing;

ll bit[300003];
ll mountains[300001];
ll mountains1[300001];
ll left1[300001];
ll right1[300001];

ll calculate(int a) {
	ll amount = 0;
	while (a > 0) {
		amount += bit[a];
		a -= (a & -a);
	}
	return amount;
}

void update(int a) {
	while (a <= 300003) {
		bit[a] += 1;
		a += (a & -a);
	}
}

int main() {
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	ll n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		ll a;
		cin >> a;
		mountains[i] = a;
		mountains1[i] = a;
	}
	sort(mountains1, mountains1+n);
	ll counter = 1;
	for (int i = 0; i < n; i++) {
		if (normalizing.find(mountains1[i]) == normalizing.end()) {
			normalizing[mountains1[i]] = counter;
			counter++;
		}
	}
	for (int i = 0; i < n; i++) {
		mountains[i] = normalizing[mountains[i]];
	}
	/*for (int i = 0; i < n; i++) {
		cout << mountains[i] << endl;
	}*/
	for (int i = 0; i < n; i++) {
		left1[i] = calculate(mountains[i]-1);
		update(mountains[i]);
	}
	/*for (int i = 0; i < n; i++) {
		cout << left1[i] << endl;
	}*/
	for (int i = 0; i < 300003; i++) {
		bit[i] = 0;
	}
	for (int i = n-1; i >= 0; i--) {
		right1[i] = calculate(mountains[i]-1);
		update(mountains[i]);
	}
	/*for (int i = 0; i < n; i++) {
		cout << right1[i] << endl;
	}*/
	ll answer = 0;
	for (int i = 0; i < n; i++) {
		answer += left1[i]*right1[i];
	}
	cout << answer << endl;
}

• 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