Submission #401690

#TimeUsernameProblemLanguageResultExecution timeMemory
401690priyansh5525Mountains (NOI20_mountains)C++17
6 / 100
105 ms50608 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...