Submission #1227515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227515		NAMIN	Construction of Highway (JOI18_construction)	C++20	16 / 100	2095 ms	7956 KiB

construction

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define ll long long

int N;

struct STsum{
	int len = 1;
	vector<int> tree;
	
	STsum(int l){
		while(len<l){
			len *=2;
		}
		tree = vector<int>(len*2,0);
	}
	
	void add(int idx){
		idx += len;
		tree[idx]++;
		for(idx/=2;idx>=1;idx/=2){
			tree[idx]=tree[idx*2]+tree[idx*2+1];
		}
	}
	int get(int r){
		int l=len;
		r+=len;
		int res = 0;	
		while(l<=r){
			if(l%2==1){
				res += tree[l++];
			}
			if(r%2==0){
				res += tree[r--];
			}
			l/=2,r/=2;
		}
		return res;
	}
};

int main(){
	cin >> N;
	vector<pair<int,int>> C(N);
	for(int i=0;i<N;i++){
		cin >> C[i].first;
		C[i].second = i;
	}
	
	sort(C.begin(),C.end());
	int curColor=1;
	map<int,int> cor;
	for(int i=0;i<N;i++){
		if(cor[C[i].first]==0){
			cor[C[i].first]=curColor++;
		}
	}
	for(int i=0;i<N;i++){
		C[i].first=cor[C[i].first];
	}
	sort(C.begin(),C.end(),[&](const pair<int,int>&a,const pair<int,int>&b){
		return a.second<b.second;
	});

	vector<int> color(N,0);
	color[0]=C[0].first;
	vector<int> parent(N,-1);
	for(int i=0;i<N-1;i++){
		int u,v;
		cin >> u >> v;
		u--,v--;
		int nxtColor = C[v].first;
		color[v]=nxtColor;
		int node=u;
		STsum seg(N+1);
		ll res = 0;
		while(node!=-1){
			//cout << node+1 << ":" << color[node] << "->";
			seg.add(color[node]);
			res += seg.get(color[node]-1);
			color[node]=nxtColor;
			node = parent[node];
		}
		//cout << endl;
		parent[v]=u;

		cout << res << endl;
	}
}

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