Submission #472625

#	Time	Username	Problem	Language	Result	Execution time	Memory
472625		kungfulon	Mountains (NOI20_mountains)	C++17	100 / 100	354 ms	15280 KiB

Mountains

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
long long low[300001],high[300001];
long long ans = 0;
long long a[300001];

void ulow(int x){
	for(;x<=n;x += x&-x){
		low[x]++;
	}
}

long long glow(int x){
	long long s = 0;
	for(;x;x -= x&-x){
		s += low[x];
	}
	return s;
}

void uhigh(int x,long long v){
	for(;x;x -= x&-x){
		high[x]+=v;
	}
}

long long ghigh(int x){
	long long s = 0;
	for(;x<=n;x += x&-x){
		s += high[x];
	}
	return s;
}

int main(int argc,const char** argv){
    cin >> n;
    for(int i = 0;i < n;i++) cin >> a[i];
    vector<long long> r(a,a+n);
	sort(r.begin(),r.end());
	r.resize(unique(r.begin(),r.end()) - r.begin());
	for(int i = 0;i < n;i++) a[i] = lower_bound(r.begin(),r.end(),a[i]) - r.begin() + 1;
	for(int i = 0;i < n;i++){
		long long u = glow(a[i]-1);
		ulow(a[i]);
		long long v = ghigh(a[i]+1);
		uhigh(a[i],u);
		ans += v;
	}
	cout << ans;
}

• 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