제출 #1172699

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172699		Nurislam	Construction of Highway (JOI18_construction)	C++20	0 / 100	0 ms	324 KiB

construction

#include <bits/stdc++.h>

using namespace std;


#define int long long
#define pb push_back

int inf = 1e18; 

const int mod = 1e9 + 7;

struct bitt {
	vector<int> t;
	int n;
	bitt (int N) : n(N+1) {
		t.resize(n+2);
	};
	
	void upd(int i, int va) { i ++ ;
		for(; i < n; i += (i & -i)) t[i] += va;
	};
	
	int get(int i) { i ++ ;
		int res = 0;
		for(; i > 0; i -= (i & -i)) res += t[i];
		return res;
	};
	
	int get(int l, int r) { r--;
		return get(r ) - get( -- l );
	};
};

void solve(){
	int n; cin >> n;
	
	vector<int> a(n+1);
	for(int i = 1; i <= n; i++ )cin >> a[i];
	
	vector<int> b = a;
	sort(b.begin(), b.end());
	b.erase(unique(b.begin(), b.end()), b.end());
	for(int i = 1; i <= n; i ++ )a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
	
	vector<int> pr(n+1, 1), us(n+1, 0);
	us[1] = 1;
	for(int i = 1; i < n; i++ ) {
		int u, v;
		cin >> u >> v;
		
		if(!us[u] || us[v])continue;
		
		pr[v] = u;
		vector<int> ord;
		int x = v;
		while(x != 1) ord.push_back(x = pr[x]);
		reverse(ord.begin(), ord.end());
		
		int ans = 0, cnt = 0;
		bitt t(n);
		for(int x : ord) {
			ans += cnt - t.get(a[x]);
			cnt ++ ;
			t.upd(a[x], 1);
		};
		cout << ans << '\n';
		for(int x : ord)
			a[x] = a[v];
		us[v] = 1;
	};
};

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	int tt = 1;
	//cin >> tt;
	
	while(tt -- ){
		solve();
	};
	
};

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