Submission #569892

#	Time	Username	Problem	Language	Result	Execution time	Memory
569892		jrodsc	Mountains (NOI20_mountains)	C++17	100 / 100	933 ms	79996 KiB

Mountains

#include <bits/stdc++.h>
#define INF 1000000000
#define ll long long
#define MAX_N 300005

using namespace std;

struct SegmentTree{
	ll s = 0;
	
	SegmentTree * left = NULL, * right = NULL;
	
	SegmentTree(int l,int r,vector<int> &a){
		if(l == r){
			s = (ll)a[l];
		}else{
			int mid = (l+r)/2;
			left = new SegmentTree(l,mid,a);
			right = new SegmentTree(mid+1,r,a);
			
			s = left->s + right->s;
		}
	}
	
	void upd(int l,int r,int p,int k){
		if(l == p && r == p){
			s += k;
			//cout << l << ' ' << r << ' ' << s << endl;
		}
		else{
			int mid = (l+r)/2;
			if(p <= mid)
				left->upd(l,mid,p,k);
			else
				right->upd(mid+1,r,p,k);
			
			s = left->s + right->s;
		}
	}
	
	ll rsq(int l,int r,int ss,int e){
		if(l >= ss && r <= e)
			return s;
		else if(l > e || r < ss)
			return 0;
		else{
			int mid = (l+r)/2;
			return left->rsq(l,mid,ss,e) + right->rsq(mid+1,r,ss,e);
		}
	}
};

int main(){	
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	
	cin >> n;
	
	ll h[n];
	
	set<ll> s;
	map<ll,int> trlt;
	for(int i = 0; i < n; i++){
		cin >> h[i];
		s.insert(h[i]);
	}
	
	int c = 0;
	for(auto x : s){
		trlt[x] = c++;
	}
	
	for(int i = 0; i < n; i++){
		h[i] = trlt[h[i]];
	}
	
	vector<int> a(MAX_N+1,0);
	
	SegmentTree st_left(0,MAX_N,a);
	
	for(int i = 0; i < n; i++){
		a[h[i]]++;
	}
	
	SegmentTree st_right(0,MAX_N,a);
	
	st_left.upd(0,MAX_N,h[0],1);
	st_right.upd(0,MAX_N,h[0],-1);
	st_right.upd(0,MAX_N,h[1],-1);
	
	ll ans = 0;
	
	for(int i = 1; i < n-1; i++){
		if(h[i] > 0) ans += st_left.rsq(0,MAX_N,0,h[i]-1) * st_right.rsq(0,MAX_N,0,h[i]-1);
		st_left.upd(0,MAX_N,h[i],1);
		st_right.upd(0,MAX_N,h[i+1],-1);
	}
	
	cout << ans << endl;
	
	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