Submission #718613

#	Time	Username	Problem	Language	Result	Execution time	Memory
718613		NothingXD	Construction of Highway (JOI18_construction)	C++17	0 / 100	2 ms	2772 KiB

construction

/*

   Wei Wai Wei Wai
   Zumigat nan damu dimi kwayt rayt

*/

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

typedef long long ll;
typedef double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;
/*typedef __uint128_t L;
  struct FastMod {
  ull b, m;
  FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
  ull reduce(ull a) {
  ull q = (ull)((L(m) * a) >> 64);
  ull r = a - q * b; // can be proven that 0 <= r < 2*b
  return r >= b ? r - b : r;
  }
  };
  FastMod FM(2);*/
void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e5 + 10;

int n, a[maxn], f[maxn], sz[maxn], chn[maxn], par[maxn], st[maxn], en[maxn], val[maxn], Q[maxn], tme;
vector<int> g[maxn], num;
vector<pii> ans;
set<pair<pii,int>> seg;

void add(int idx, int x){
	for (; idx <= n; idx += idx & -idx) f[idx] += x;
}

int get(int idx){
	int res = 0;
	for (; idx; idx -= idx & -idx) res += f[idx];
	return res;
}

int get(int l, int r){
	if (r < l) return 0;
	return get(r) - get(l-1);
}

void dfs(int v, int p = -1){
	par[v] = p;
	sz[v] = 1;
	for (auto u: g[v]){
		dfs(u, v);
		sz[u] += sz[v];
	}
}

void hld(int v, int c){
	st[v] = ++tme;
	chn[v] = c;
	int bc = -1;
	for (auto u: g[v]) if (bc == -1 || sz[bc] < sz[u]) bc = u;
	if (bc != -1) hld(bc, c);
	for (auto u: g[v]) if (u != bc) hld(u, u);
	en[v] = tme;
}

void change(int l, int r, int x){
	vector<pii> res;
	auto it = seg.lower_bound({{l, 0}, 0});
	if (it != seg.begin()){
		it--;
		pair<pii,int> tmp = *it;
		if (tmp.F.S >= l){
			res.push_back({tmp.S, tmp.F.S - l + 1});
			seg.erase(it);
			seg.insert({{tmp.F.F, l-1}, tmp.S});
		}
	}
	while(!seg.empty()){
		auto it = seg.lower_bound({{l, 0}, 0});
		if (it == seg.end() || (*it).F.F > r) break;
		pair<pii,int> tmp = *it;
		if (tmp.F.S <= r){
			res.push_back({tmp.S, tmp.F.S - tmp.F.F + 1});
			seg.erase(it);
		}
		else{
			res.push_back({tmp.S, r - tmp.F.F + 1});
			seg.erase(it);
			seg.insert({{r+1, tmp.F.S}, tmp.S});
		}
	}
	seg.insert({{l, r}, x});
	reverse(all(res));
	for (auto x: res) ans.push_back(x);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	cin >> n;

	for (int i = 1; i <= n; i++){
		cin >> a[i];
		num.push_back(a[i]);
	}

	sort(all(num));
	num.resize(distance(num.begin(), unique(all(num))));

	for (int i = 1; i <= n; i++){
		a[i] = lower_bound(all(num), a[i]) - num.begin() + 1;
	}

	for (int i = 1; i < n; i++){
		int x; cin >> x >> Q[i];
		g[x].push_back(Q[i]);
	}

	dfs(1);
	hld(1, 1);
	for (int i = 1; i <= n; i++){
		seg.insert({{st[i], st[i]}, a[i]});
	}

	for (int i = 1; i < n; i++){
		ans.clear();
		int v = par[Q[i]];
		while(v != -1){
			change(st[chn[v]], st[v], a[Q[i]]);
			v = par[chn[v]];
		}
		reverse(all(ans));
		ll res = 0;
		for (auto [x, y]: ans){
			res += get(x+1, n);
			add(x, y);
		}
		cout << res << '\n';
		for (auto [x, y]: ans){
			add(x, -y);
		}
	}

	return 0;
}

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