Submission #129092

#	Time	Username	Problem	Language	Result	Execution time	Memory
129092		ZwariowanyMarcin	Construction of Highway (JOI18_construction)	C++14	100 / 100	513 ms	17624 KiB

construction

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define mp make_pair
#define pb push_back
#define ld long double
#define ss(x) (int) x.size()
#define FOR(i, n) for(int i = 1; i <= n; ++i) 
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl;
 
 
using namespace std;
using namespace __gnu_pbds;
 
// order_by_key
// find_by_order
// tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> siema;

const int nax = 100005, pod = (1 << 17);
int n, a, b;
vector <int> v[nax];
int val[nax];
int q[nax][2], h[nax];
int in[nax], fre = 1, out[nax];
int P[nax];

void dfs(int u, int p) {
	in[u] = fre++;
	for(auto it: v[u]) {
		if(it != p) {
			P[it] = u;
			h[it] = h[u] + 1;
			dfs(it, u);
		}
	}
	out[u] = fre;
}

int up[nax];

struct drzewo {
	pair<int, int> d[2 * pod];
	void init() {
		for(int i = 0; i < 2 * pod; ++i)
			d[i] = mp(0, 0);
	}
	void add(int pos, int u, int ile) {
		d[pos + pod] = mp(ile, u);
		pos += pod;
		pos /= 2;
		while(pos) {
			d[pos] = max(d[2 * pos], d[2 * pos + 1]);
			pos /= 2;
		}
	}
	pair<int, int> maxi(int l, int r) {
		pair <int, int> res = mp(0, 0);
		for(l += pod, r += pod; l < r; l /= 2, r /= 2) {
			if(l & 1)
				res = max(res, d[l++]);
			if(r & 1)
				res = max(res, d[--r]);
		}
		return res;
	}
};

struct fen {
	int d[nax];
	void init() {
		for(int i = 0; i < nax; ++i)
			d[i] = 0;
	}
	void add(int pos, int x) {
		for(; pos < nax; pos += pos & -pos) {
			d[pos] += x;
		}
	}
	int daj(int x) {
		int res = 0;
		for(; x > 0; x -= x & -x) {
			res += d[x];
		}
		return res;
	}
};

fen F;
drzewo D;
			
vector <pair<int, int>> mam;

vector <int> war;

ll akt(int u) {
	mam.clear();
	int ans = 0;
	while(u != 0 && D.maxi(in[u], out[u]).fi == 0) {
		ans += F.daj(val[u] - 1);
		F.add(val[u], 1);
		mam.pb(mp(val[u], -1));
		u = P[u];
	}
	
	while(u != 0) {
		int color = D.maxi(in[u], out[u]).se;
		int ile = h[u] - h[up[color]];
		ans += (ll) F.daj(val[color] - 1) * ile;
		F.add(val[color], ile);
		mam.pb(mp(val[color], -ile));
		int D = up[color];
		up[color] = u;
		u = D;
	}
	for(auto it: mam)
		F.add(it.fi, it.se);
	return ans;
}
		


int main() {
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	
	F.init();
	D.init();	
	h[0] = -1;
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &val[i]);
		war.pb(val[i]);
	}
	
	sort(war.begin(), war.end());
	for(int i = 1; i <= n; ++i)
		val[i] = lower_bound(war.begin(), war.end(), val[i]) - war.begin() + 1;
	
	
	for(int i = 1; i <= n - 1; ++i) {
		scanf("%d%d", &q[i][0], &q[i][1]);
		v[q[i][0]].pb(q[i][1]);
		v[q[i][1]].pb(q[i][0]);
	}
	
	dfs(1, 0);
	
	for(int i = 1; i < n; ++i) {
		printf("%lld\n", akt(q[i][0]));
		D.add(in[q[i][1]], q[i][1], i);
	}
	
	
	
	
	
	
	
	
	return 0;
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:133:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
construction.cpp:135:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &val[i]);
   ~~~~~^~~~~~~~~~~~~~~
construction.cpp:145:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &q[i][0], &q[i][1]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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