Submission #239382

#	Time	Username	Problem	Language	Result	Execution time	Memory
239382		jtnydv25	Construction of Highway (JOI18_construction)	C++17	100 / 100	1163 ms	34936 KiB

construction

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

#define ll long long
#define sd(x) scanf("%d", &(x))
#define pii pair<int, int>
#define F first
#define S second
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#define ld long double

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<", "<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"{";
	for(int i = 0;i < (int)v.size(); i++){
		if(i)os<<", ";
		os<<v[i];
	}
	os<<"}";
	return os;
}

#ifdef LOCAL
#define cerr cout
#else
#endif

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
const int N = 100005;
const int logN = 20;

int arrival[N], par[logN][N], depth[N], A[N], B[N], C[N];
int st[N], en[N], timer;

vector<int> children[N];
void dfs(int s, int d){
	depth[s] = d;
	st[s] = timer++;
	for(int v : children[s]) dfs(v, d + 1);
	en[s] = timer - 1;
}

// 0-indexed
template<class T>
struct segtree{
	int n;
	vector<T> t;
	T def;
	inline T combine(T a, T b){
		return arrival[a] > arrival[b] ? a : b;
	}

	segtree(vector<T> & inp, T def = T()) : n(sz(inp)), def(def){
		t.resize(2 * n, def);
		for(int i = 0; i < n; i++) t[n + i] = inp[i];
		for(int i = n - 1; i > 0; --i) t[i] = combine(t[i<<1], t[i<<1|1]);
	}

	void modify(int p, T value) { // modify a[p] = value
		// value = combine(value, t[p + n]); // if a[p] = combine(a[p], value)
		for (t[p += n] = value; p >>= 1; ) t[p] = combine(t[p<<1], t[p<<1|1]);
	}

	T query(int l, int r) {  // compute on interval [l, r]
    r++;
		T resl = def, resr = def;
		for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if (l&1) resl = combine(resl, t[l++]);
			if (r&1) resr = combine(t[--r], resr);
		}
		return combine(resl, resr);
	}
};

ll bit[N];
void add(int x, int y){
	x++;
	for(; x < N; x += x & -x) bit[x] += y;
}

ll get(int x){
	x++;
	ll ret = 0;
	for(; x; x -= x & -x) ret += bit[x];
	return ret;
}

ll get(int l, int r){
	return get(r) - get(l - 1);
}

int getKth(int x, int k){
	for(int i = 0; i < logN; i++) if(k >> i & 1) x = par[i][x];
	return x;
}

int main(){
	int n; sd(n);
	vector<int> V(n);
	segtree<int> stree(V);
	map<int, int> compress; set<int> vals;

	for(int i = 0; i < n; i++){
		sd(C[i]);
		vals.insert(C[i]);
	}

	int pos = 0;
	for(int v : vals) compress[v] = pos++;

	for(int i = 0; i < n; i++) C[i] = compress[C[i]];

	for(int i = 1; i < n; i++){
		sd(A[i]); sd(B[i]);
		A[i]--; B[i]--;
		arrival[B[i]] = i;
		par[0][B[i]] = A[i];
		children[A[i]].push_back(B[i]);
	}
	dfs(0, 0);
	for(int j = 1; j < logN; j++) for(int i = 0; i < n; i++) par[j][i] = par[j - 1][par[j - 1][i]];

	for(int i = 1; i < n; i++){
		int x = B[i];
		int curr = 1;
		vector<pii> vec;
		ll num = 0;
		while(curr <= depth[x]){
			int y = getKth(x, curr);
			int latestNode = stree.query(st[y], en[y]); // last added in x's subtree
			// maximum with the same value
			int lo = curr, hi = depth[x];
			while(lo < hi){
				int mid = (lo + hi + 1) >> 1;
				int node = getKth(x, mid);
				if(stree.query(st[node], en[node]) == latestNode) lo = mid;
				else hi = mid - 1;
			}
			int v = C[latestNode], cnt = lo - curr + 1;

			vec.push_back({v, cnt}); // v comes cnt times

			num += cnt * (ll) get(0, v - 1); // the values below should be smaller than this

			add(v, cnt);
			curr = lo + 1;
		}
		for(auto it : vec) add(it.F, -it.S); // reinitialize bit to 0
		printf("%lld\n", num);
		
		stree.modify(st[x], x);
	}
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
construction.cpp:119:9: note: in expansion of macro 'sd'
  int n; sd(n);
         ^~
construction.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
construction.cpp:125:3: note: in expansion of macro 'sd'
   sd(C[i]);
   ^~
construction.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
construction.cpp:135:3: note: in expansion of macro 'sd'
   sd(A[i]); sd(B[i]);
   ^~
construction.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
construction.cpp:135:13: note: in expansion of macro 'sd'
   sd(A[i]); sd(B[i]);
             ^~

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