Submission #401662

#	Time	Username	Problem	Language	Result	Execution time	Memory
401662		priyansh5525	Mountains (NOI20_mountains)	C++17	0 / 100	83 ms	20548 KiB

Mountains

#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
#define vi vector <long long int >
#define pii pair<long long int, long long int>
#define pb push_back
#define pf push_front
#define mod 1000000007
#define ff fflush()
ll n;
struct node {
	ll val;
	ll freq;
	ll h,pop;
	struct node *l;
	struct node *r;
};

struct node *root = new node;

ll findPop(struct node *cur){
	if(cur==NULL){
		return 0;
	}
	else
		return cur->pop;
}
ll findH(struct node *cur){
	if(cur==NULL){
		return 0;
	}
	else
		return cur->h;
}

struct node * rightRotate(struct node *cur){
	struct node *tmp = cur->l;
	struct node *tmp2 = tmp->r;
	tmp->r = cur;
	cur->l = tmp2;
	cur->pop = cur->freq+ findPop(cur->l)+findPop(cur->r);
	tmp->pop = tmp->freq + findPop(tmp->l)+ findPop(tmp->r);
	cur->h = max(findH(cur->l),findH(cur->r)) + 1;
	tmp->h = max(findH(tmp->l),findH(tmp->r))+1;
	return tmp;
}
struct node * leftRotate(struct node *cur){
	struct node *tmp = cur->r;
	struct node *tmp2 = tmp->l;
	tmp->l = cur;
	cur->r = tmp2;
	cur->pop = cur->freq+ findPop(cur->l)+findPop(cur->r);
	tmp->pop = tmp->freq + findPop(tmp->l)+ findPop(tmp->r);
	cur->h = max(findH(cur->l),findH(cur->r)) + 1;
	tmp->h = max(findH(tmp->l),findH(tmp->r))+1;
	return tmp;
}

struct node * insert(struct node *cur , ll val, ll *sc){
	if(cur->val == val){
		cur->freq++;
		cur->pop++;
		(*sc)+=findPop(cur->l);
		return cur; 
	}
	else if((cur->val)>val){
		if(cur->l==NULL){
			struct node *tmp = new node;
			tmp->val = val;
			tmp->freq = 1;
			tmp->h = 1;
			tmp->pop = 1;
			cur->h = 2;
			cur->pop++;
			cur->l = tmp;
			return cur;
		}
		cur->l = insert(cur->l, val , sc);
		ll x = findH(cur->l);
		ll y = findH(cur->r);
		if(x-y>1){
			cur = rightRotate(cur);
		}
		if(y-x>1)
			cur = leftRotate(cur);
		return cur;
	}
	else{
		if(cur->r==NULL){
			struct node *tmp = new node;
			tmp->val = val;
			tmp->freq = 1;
			tmp->h = 1;
			tmp->pop = 1;
			cur->h = 2;
			cur->pop++;
			cur->r = tmp;
			(*sc)+=findPop(cur->l)+cur->freq;
			return cur;
		}
		(*sc) += findPop(cur->l)+cur->freq;
		cur->r = insert(cur->r,val,sc);
		ll x = findH(cur->l), y = findH(cur->r);
		if(x-y>1){
			cur = rightRotate(cur);
		}
		if(y-x>1){
			cur = leftRotate(cur);
		}
		return cur;
	}
}

void bst(ll val,ll *arr, ll i){
	ll score = 0;
	insert(root,val,&score);
	arr[i] = score;
}

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);	
    cin>>n;
   	ll x;
   	vi a;
   	ll left[n], right[n];
   	for(ll i=0;i<n;i++){
   		cin>>x;
   		a.pb(x);
   	}
   	root->val = a[0];root->freq = 1; root->pop = 1; left[0] = 0;
   	for(ll i=1;i<n;i++){
   		bst(a[i], left , i);
   	}
  	root->val = a[n-1]; root->freq = 1; root->pop = 1; right[n-1] = 0; root->l = NULL; root->r = NULL;
  	for(ll i=n-2;i>=0;i--){
  		bst(a[i],right,i);
  	}
  	ll ans = 0;
  	for(ll i=0;i<n-1;i++){
  		ans += left[i]*right[i];
  	}
  	cout<<ans<<"\n";
	return 0;
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 9
• Subtask 4: 0 / 36
• Subtask 5: 0 / 28
• Subtask 6: 0 / 9
• Subtask 7: 0 / 12