Submission #545353

#	Time	Username	Problem	Language	Result	Execution time	Memory
545353		Trisanu_Das	Mountains (NOI20_mountains)	C++17	100 / 100	466 ms	45948 KiB

Mountains

#include<bits/stdc++.h>
using namespace std;
struct node{
	int s, e, m, cnt;
	node *l, *r;
	node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2), cnt(0){
		if(s == e) return;
		l = new node(s, m);
		r = new node(m+1, e);
	}
	void update(int x, int v){
		cnt += v;
		if(s == e) return;
		if(x <= m) l->update(x, v);
		else r->update(x, v);
	}
	int query(int x, int y){
		if(x <= s && y >= e) return cnt;
		int ret = 0;
		if(x <= m) ret += l->query(x, y);
		if(y >= m+1) ret += r->query(x, y);
		return ret;
	}
	void clear(){
		cnt = 0;
		if(s == e) return;
		l->clear();
		r->clear();
	}
};

long long leftof[300001], rightof[300001];
pair<long long, int> distinctArr[300001];
int cnt = 1;
long long solve(int n, long long H[]){
	for(int i = 1; i <= n; i++) distinctArr[i] = {H[i], i};
	sort(distinctArr + 1, distinctArr + n + 1);

	for(int i = 1; i <= n; i++){
		if (i > 1 && distinctArr[i].first != distinctArr[i-1].first) cnt++;
		H[distinctArr[i].second] = cnt;
	}
	
	node *root = new node(0, n);
	for(int i = 1; i <= n; i++){
		leftof[i] = root->query(0, H[i] - 1);
		root->update(H[i], 1);
	}
	
	root->clear();
	for(int i = n; i > 0; i--){
		rightof[i] = root->query(0, H[i] - 1);
		root->update(H[i], 1);
	}
	
	long long total = 0;
	for(int i = 1; i <= n; i++){
		total += leftof[i] * rightof[i];
	}
	
	return total;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	long long H[300001];
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> H[i];
	long long total = solve(n, H);
	cout << total;
	return 0;
}

• 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