Submission #101042

#	Time	Username	Problem	Language	Result	Execution time	Memory
101042		ecasdqina	Construction of Highway (JOI18_construction)	C++14	16 / 100	2058 ms	5096 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, lazy;
	int sz = 1;
	
	SegmentTree(int n) {
		while(sz < n) sz <<= 1;
		seg.assign(sz * 2, 0);
	}
	void add(int k, int x = 1) {
		k += sz;
		seg[k] += x;
		
		while(k >>= 1) seg[k] = seg[2 * k + 0] + seg[2 * k + 1];
	}
	i64 get(int a, int b) {
		i64 L = 0, R = 0;
		for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
			if(a & 1) L = L + seg[a++];
			if(b & 1) R = seg[--b] + R;
		}
		return L + R;
	}
	i64 operator[](int k) {
		return seg[k + sz];
	}
};

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:36: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:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &c[i]);
   ~~~~~^~~~~~~~~~~~~
construction.cpp:45: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