Submission #101031

#	Time	Username	Problem	Language	Result	Execution time	Memory
101031		ecasdqina	Construction of Highway (JOI18_construction)	C++14	16 / 100	939 ms	1024 KiB

construction

#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

struct SegmentTree {
	std::vector<i64> seg;
	int sz = 1;
	
	SegmentTree(int n) {
		while(sz < n) sz <<= 1;
		seg.assign(sz * 2 - 1, 0);
	}
	void add(int k, int x = 1) {
		k += sz - 1;
		seg[k] += x;
		
		while(k) {
			k = (k - 1) >> 1;
			
			seg[k] = seg[2 * k + 1] + seg[2 * k + 2];
		}
	}
	void update(int k, int x = 1) {
		k += sz - 1;
		seg[k] = x;
		
		while(k) {
			k = (k - 1) >> 1;
			
			seg[k] = seg[2 * k + 1] + seg[2 * k + 2];
		}
	}
	i64 get(int a, int b, int k, int l, int r) {
		if(b <= l || r <= a) return 0;
		if(a <= l && r <= b) return seg[k];
		
		i64 L = get(a, b, 2 * k + 1, l, (l + r) >> 1);
		i64 R = get(a, b, 2 * k + 2, (l + r) >> 1, r);
		return L + R;
	}
	i64 get(int a, int b) {
		return get(a, b, 0, 0, sz);
	}
	i64 operator[](int k) {
		return seg[k + sz - 1];
	}
};

int main() {
	int n; scanf("%d", &n);
	std::vector<int> c(n), a(n - 1), b(n - 1), latte;
	std::vector<int> number(n, -1);
	for(int i = 0; i < n; i++) {
		scanf("%d", &c[i]);
		
		latte.push_back(c[i]);
	}
	for(int i = 0; i < n - 1; i++) {
		scanf("%d%d", &a[i], &b[i]);
		a[i]--; b[i]--;
		
		number[b[i]] = i;
	}
	sort(begin(latte), end(latte)); latte.erase(unique(begin(latte), end(latte)), end(latte));
	
	std::function<int (int)> getIndex = [&](int v) {
		return lower_bound(begin(latte), end(latte), v) - begin(latte);
	};
	
	assert(n <= 4000);
	
	std::vector<int> parent(n, -1);
	for(int i = 0; i < n - 1; i++) {
		i64 ans = 0;
		int now = a[i];
		SegmentTree seg(latte.size());
		while(now != -1) {
			int k = getIndex(c[now]);
			ans += seg.get(0, k);
			seg.add(k);
			
			c[now] = c[b[i]];
			now = parent[now];
		}
		parent[b[i]] = a[i];
	
		printf("%lld\n", ans);
	//	for(auto v: c) cout << v << " "; cout << endl;
	}
	
	return 0;
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n; scanf("%d", &n);
         ~~~~~^~~~~~~~~~
construction.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &c[i]);
   ~~~~~^~~~~~~~~~~~~
construction.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a[i], &b[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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