oj.uz

Submission #401721

# Submission time Handle Problem Language Result Execution time Memory
401721 2021-05-10T18:11:10 Z priyansh5525 Mountains (NOI20_mountains) C++17
6 / 100
 126 ms 44932 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);
		cur->pop = findPop(cur->l)+findPop(cur->r)+cur->freq;
		ll x = findH(cur->l);
		ll y = findH(cur->r);
		cur->h = max(x,y)+1;
		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);
		cur->pop = findPop(cur->l)+findPop(cur->r)+cur->freq;
		ll x = findH(cur->l), y = findH(cur->r);
		cur->h = max(x,y)+1;
		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;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 100 ms 44816 KB Output is correct
3 Correct 126 ms 44896 KB Output is correct
4 Correct 96 ms 44932 KB Output is correct
5 Correct 97 ms 44848 KB Output is correct
6 Correct 100 ms 44860 KB Output is correct
7 Correct 103 ms 44876 KB Output is correct
8 Correct 102 ms 44872 KB Output is correct
9 Correct 94 ms 34472 KB Output is correct
10 Correct 95 ms 34540 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 9192 KB Output is correct
2 Correct 38 ms 9236 KB Output is correct
3 Correct 35 ms 9184 KB Output is correct
4 Correct 35 ms 9196 KB Output is correct
5 Correct 41 ms 9232 KB Output is correct
6 Correct 36 ms 9152 KB Output is correct
7 Correct 37 ms 9224 KB Output is correct
8 Correct 32 ms 9156 KB Output is correct
9 Correct 31 ms 9204 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 35 ms 9192 KB Output is correct
2 Correct 38 ms 9236 KB Output is correct
3 Correct 35 ms 9184 KB Output is correct
4 Correct 35 ms 9196 KB Output is correct
5 Correct 41 ms 9232 KB Output is correct
6 Correct 36 ms 9152 KB Output is correct
7 Correct 37 ms 9224 KB Output is correct
8 Correct 32 ms 9156 KB Output is correct
9 Correct 31 ms 9204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Incorrect 79 ms 22704 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 35 ms 9192 KB Output is correct
2 Correct 38 ms 9236 KB Output is correct
3 Correct 35 ms 9184 KB Output is correct
4 Correct 35 ms 9196 KB Output is correct
5 Correct 41 ms 9232 KB Output is correct
6 Correct 36 ms 9152 KB Output is correct
7 Correct 37 ms 9224 KB Output is correct
8 Correct 32 ms 9156 KB Output is correct
9 Correct 31 ms 9204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Incorrect 79 ms 22704 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 100 ms 44816 KB Output is correct
3 Correct 126 ms 44896 KB Output is correct
4 Correct 96 ms 44932 KB Output is correct
5 Correct 97 ms 44848 KB Output is correct
6 Correct 100 ms 44860 KB Output is correct
7 Correct 103 ms 44876 KB Output is correct
8 Correct 102 ms 44872 KB Output is correct
9 Correct 94 ms 34472 KB Output is correct
10 Correct 95 ms 34540 KB Output is correct
11 Correct 35 ms 9192 KB Output is correct
12 Correct 38 ms 9236 KB Output is correct
13 Correct 35 ms 9184 KB Output is correct
14 Correct 35 ms 9196 KB Output is correct
15 Correct 41 ms 9232 KB Output is correct
16 Correct 36 ms 9152 KB Output is correct
17 Correct 37 ms 9224 KB Output is correct
18 Correct 32 ms 9156 KB Output is correct
19 Correct 31 ms 9204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Incorrect 79 ms 22704 KB Output isn't correct
22 Halted 0 ms 0 KB -