oj.uz

Submission #401662

# Submission time Handle Problem Language Result Execution time Memory
401662 2021-05-10T16:18:52 Z priyansh5525 Mountains (NOI20_mountains) C++17
0 / 100
 83 ms 20548 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Runtime error 83 ms 20548 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 15700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 15700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 452 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 452 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 15700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Runtime error 83 ms 20548 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -