#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int lld;
int FT[1000000];
int sz;
void init(int n){sz=n;
for(int i=0;i<=n;i++)FT[i]=0;
}
void update(int pos){
pos++;
for(;pos<=sz;pos+=((pos)&(-pos))){
FT[pos]++;
}
}
int query(int pos){
pos++;
int ans=0;
for(;pos>0;pos-=((pos)&(-pos))){
ans+=FT[pos];
}return ans;
}
void print(){
for(int i=0;i<sz;i++)cout<<FT[i]<<" ";
cout<<endl;
}
lld analyse(vector<int> v){
int n=v.size();
pair<int,int> arr[n];
for(int i=0;i<n;i++){//cout<<v[i]<<" ";
arr[i].first=v[i];
arr[i].second=i;
}//cout<<endl;
sort(arr,arr+n);
int prev=0;
init(n);
lld ans=0;
for(int i=0;i<=n;i++){
if(i==n ||(i>0 && arr[i].first>arr[i-1].first)){
for(int j=prev;j<i;j++){
ans+=query(arr[j].second);
}
for(int j=prev;j<i;j++){
update(arr[j].second);
}
prev=i;
}
}//print();
return ans;
}
int main(){
int n;
cin>>n;
int C[n];
for(int i=0;i<n;i++){
cin>>C[i];
}
int parent[n];
parent[0]=0;
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
x--;
parent[i]=x;
vector<int> v;
int pnt=i;
while(pnt!=0){
pnt=parent[pnt];
v.push_back(C[pnt]);
C[pnt]=C[i];
}
cout<<analyse(v)<<endl;
}
/*for(int i=0;i<n;i++){
cout<<C[i]<<endl;
}*/
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
760 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
760 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
760 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
