Submission #73179

#	Time	Username	Problem	Language	Result	Execution time	Memory
73179		KLPP	Construction of Highway (JOI18_construction)	C++14	16 / 100	2066 ms	13500 KiB

construction

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
typedef long long int lld;
int FT[10000];
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--;
		y--;
		parent[y]=x;
		vector<int> v;
		int pnt=y;
		while(pnt!=0){
			pnt=parent[pnt];
			v.push_back(C[pnt]);
			C[pnt]=C[y];
		}
		cout<<analyse(v)<<endl;
	}
	/*for(int i=0;i<n;i++){
		cout<<C[i]<<endl;
	}*/
	return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 0 / 84