Submission #105255

#	Time	Username	Problem	Language	Result	Execution time	Memory
105255		he_____he	Construction of Highway (JOI18_construction)	C++14	16 / 100	2033 ms	4580 KiB

construction

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int readint(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n;
int a[100005],c[100005],fa[100005],p[100005];

int lowbit(int x){return x&(-x);}
void add(int x){for(;x<=n;x+=lowbit(x))c[x]++;}
int ask(int x){int ret=0;for(;x;x-=lowbit(x))ret+=c[x];return ret;}

int main(){
	n=readint();
	for(int i=1;i<=n;i++) p[i]=a[i]=readint();
	sort(p+1,p+n+1);
	for(int i=1;i<=n;i++) a[i]=lower_bound(p+1,p+n+1,a[i])-p;
	int x,y,tx,nans;
	for(int i=1;i<=n-1;i++){
		tx=x=readint(); y=readint();
		memset(c,0,sizeof(c)); nans=0;
		while(x){
			nans+=ask(a[x]-1);
			add(a[x]);
			x=fa[x];
		}
		printf("%d\n",nans);
		fa[y]=tx,x=tx;
		while(x){
			a[x]=a[y];
			x=fa[x];
		}
	}
	return 0;
}

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