제출 #1262365

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1262365		PlayVoltz	Mountains (NOI20_mountains)	C++20	100 / 100	658 ms	110716 KiB

Mountains

#include <bits/stdc++.h>
using namespace std;

#define int long long

vector<vector<int> > segmenttree;
vector <int> vect;

vector<int> mergesort(vector<int> a, vector<int> b){
	int p1 = 0, p2 = 0;
	vector <int> temp;
	while (p1!=a.size() || p2!=b.size()){
		if (p1==a.size()){
			temp.push_back(b[p2]);
			++p2;
		}
		else if (p2==b.size()){
			temp.push_back(a[p1]);
			++p1;
		}
		else if (a[p1]>b[p2]){
			temp.push_back(b[p2]);
			++p2;
		}
		else{
			temp.push_back(a[p1]);
			++p1;
		}
	}
	return temp;
}

void build(int index, int left, int right){
	if (left==right){
		segmenttree[index] = vector<int>(1, vect[left]);
		return;
	}
	int mid = (left+right)/2;
	build(2*index+1, left, mid);
	build(2*index+2, mid+1, right);
	segmenttree[index] = mergesort(segmenttree[2*index+1], segmenttree[2*index+2]);
}

int query(int index, int left, int right, int l, int r, int val){
	if (l>r){
		return 0;
	}
	if (left==l && right==r){
		return lower_bound(segmenttree[index].begin(), segmenttree[index].end(), val)-segmenttree[index].begin();
	}
	int mid = (left+right)/2;
	return query(2*index+1, left, mid, l, min(mid, r), val)+query(2*index+2, mid+1, right, max(mid+1, l), r, val);
}
	
int32_t main(){
	int n;
	cin>>n;
	segmenttree.resize(4*n);
	vect.resize(n);
	for (int i=0; i<n; ++i){
		cin>>vect[i];
	}
	build (0, 0, n-1);
	int sum = 0;
	for (int i=1; i<n-1; ++i){
		int l = query(0, 0, n-1, 0, i-1, vect[i]), r = query(0, 0, n-1, i+1, n-1, vect[i]);
		sum+=l*r;
	}
	cout<<sum;
}

• 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