Submission #769234

#	Time	Username	Problem	Language	Result	Execution time	Memory
769234		Mohammad_Parsa	Construction of Highway (JOI18_construction)	C++17	16 / 100	143 ms	724 KiB

construction

/* in the name of allah */
#include<bits/stdc++.h>
using namespace std;

//#define endl '\n'
#define pb push_back
#define F first
#define S second
#define mk make_pair
typedef long long ll;

const int N=4e3+7;
int n,c[N],a[N],b[N],ans[N],p[N],x[N],fen[N];
pair<int,int>com[N];

void upd(int i,int x){
	for(;i<N;i+=i&(-i)){
		fen[i]+=x;
	}
}

int get(int i){
	int ans=0;
	for(;i;i-=i&(-i)){
		ans+=fen[i];
	}
	return ans;
}


int main(){
	ios:: sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>c[i];
		com[i]=mk(c[i],i);
	}
	int k=1;
	sort(com,com+n+1);
	for(int i=1;i<=n;i++){
		c[com[i].S]=k;
		if(com[i].F!=com[i+1].F)k++;
	}
	for(int i=0;i<n-1;i++){
		cin>>a[i]>>b[i];
		p[b[i]]=a[i];
	}
	x[1]=1;
	for(int i=0;i<n-1;i++){
		int u=a[i];
		x[b[i]]=b[i];
		while(u!=0){
			ans[i]+=get(c[x[u]]-1);
			upd(c[x[u]],1);
			x[u]=b[i];
			u=p[u];
		}
		fill(fen,fen+N,0);
		cout<<ans[i]<<endl;
	}
}

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