oj.uz

Submission #401690

# Submission time Handle Problem Language Result Execution time Memory
401690 2021-05-10T17:14:05 Z priyansh5525 Mountains (NOI20_mountains) C++17
6 / 100
 105 ms 50608 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;
			tmp->l = NULL; tmp->r = NULL;
			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;
			tmp->l = NULL; tmp->r = NULL;
			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; root->h = 1;left[0] = 0;root->l = NULL; root->r = NULL;
   	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;root->h = 1;
  	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
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 101 ms 44908 KB Output is correct
3 Correct 105 ms 50608 KB Output is correct
4 Correct 100 ms 50492 KB Output is correct
5 Correct 103 ms 50352 KB Output is correct
6 Correct 103 ms 50476 KB Output is correct
7 Correct 103 ms 50408 KB Output is correct
8 Correct 104 ms 50420 KB Output is correct
9 Correct 102 ms 40028 KB Output is correct
10 Correct 95 ms 40012 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 9268 KB Output is correct
2 Correct 36 ms 9792 KB Output is correct
3 Correct 37 ms 9796 KB Output is correct
4 Correct 37 ms 9744 KB Output is correct
5 Correct 37 ms 9864 KB Output is correct
6 Correct 37 ms 9848 KB Output is correct
7 Correct 38 ms 9716 KB Output is correct
8 Correct 32 ms 9708 KB Output is correct
9 Correct 31 ms 9800 KB Output is correct
10 Correct 1 ms 204 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 9268 KB Output is correct
2 Correct 36 ms 9792 KB Output is correct
3 Correct 37 ms 9796 KB Output is correct
4 Correct 37 ms 9744 KB Output is correct
5 Correct 37 ms 9864 KB Output is correct
6 Correct 37 ms 9848 KB Output is correct
7 Correct 38 ms 9716 KB Output is correct
8 Correct 32 ms 9708 KB Output is correct
9 Correct 31 ms 9800 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Incorrect 65 ms 10072 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 9268 KB Output is correct
2 Correct 36 ms 9792 KB Output is correct
3 Correct 37 ms 9796 KB Output is correct
4 Correct 37 ms 9744 KB Output is correct
5 Correct 37 ms 9864 KB Output is correct
6 Correct 37 ms 9848 KB Output is correct
7 Correct 38 ms 9716 KB Output is correct
8 Correct 32 ms 9708 KB Output is correct
9 Correct 31 ms 9800 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Incorrect 65 ms 10072 KB Output isn't correct
12 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 Correct 101 ms 44908 KB Output is correct
3 Correct 105 ms 50608 KB Output is correct
4 Correct 100 ms 50492 KB Output is correct
5 Correct 103 ms 50352 KB Output is correct
6 Correct 103 ms 50476 KB Output is correct
7 Correct 103 ms 50408 KB Output is correct
8 Correct 104 ms 50420 KB Output is correct
9 Correct 102 ms 40028 KB Output is correct
10 Correct 95 ms 40012 KB Output is correct
11 Correct 37 ms 9268 KB Output is correct
12 Correct 36 ms 9792 KB Output is correct
13 Correct 37 ms 9796 KB Output is correct
14 Correct 37 ms 9744 KB Output is correct
15 Correct 37 ms 9864 KB Output is correct
16 Correct 37 ms 9848 KB Output is correct
17 Correct 38 ms 9716 KB Output is correct
18 Correct 32 ms 9708 KB Output is correct
19 Correct 31 ms 9800 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Incorrect 65 ms 10072 KB Output isn't correct
22 Halted 0 ms 0 KB -