Submission #626552

#	Time	Username	Problem	Language	Result	Execution time	Memory
626552		codr0	Construction of Highway (JOI18_construction)	C++14	16 / 100	234 ms	724 KiB

construction

// Code by Parsa Eslami

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>

#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define all(x) x.begin(),x.end()
#define SZ(x) ((int)x.size())
#define bit(i,j) ((j>>i)&1)
#define pb push_back
#define lc 2*id
#define rc 2*id+1
#define dmid int mid=(r+l)/2
#define err(x) cerr<#x<<" : "<<x<<'\n'
#define F first
#define S second

using namespace std;
const int N=4000+4;
int par[N],val[N];
struct fenwick{
	int fen[N];
	void add(int k,int x){
		while(k>0){
			fen[k]+=x;
			k-=(k&(-k));
		}
	}
	int get(int k){
		int rt=0;
		while(k<N){
			rt+=fen[k];
			k+=(k&(-k));
		}
		return rt;
	}
};
fenwick fen;

	int Get(){
		int x; cin>>x; return x;
	}

	void Set(int v,int x){
		val[v]=x;
		if(v==1) return;
		Set(par[v],x);
	}

	ll get(int u){
		ll rt=0;
		int v=u;
		vector<int> vc;
		while(1){
			vc.pb(v);
			if(v==1) break;
			v=par[v];
		}
		reverse(all(vc));
		for(int x:vc){
			rt+=fen.get(val[x]+1);
			fen.add(val[x],+1);
		}
		for(int x:vc) fen.add(val[x],-1);
		return rt;
	}

	int32_t main(){
	iostream::sync_with_stdio(0); cin.tie(0);

	int n=Get();
	FOR(i,1,n) val[i]=Get();
	vector<pii> vc;
	FOR(i,1,n) vc.pb({val[i],i});
	sort(all(vc)); int x0=0;
	FOR(i,0,SZ(vc)-1){
		if(i==0||vc[i].F!=vc[i-1].F) x0++;
		val[vc[i].S]=x0;
	}
	FOR(i,1,n-1){
		int u=Get(),v=Get();
		cout<<get(u)<<'\n';
		par[v]=u;
		Set(u,val[v]);
	}


	return 0;
	}

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