Submission #44058

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
44058	2018-03-29T13:07:09 Z	cheater2k	Construction of Highway (JOI18_construction)	C++17	Compilation error	0 ms	0 KB

construction

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

const int N = 100005;

int n, c[N];
vector < pair<int,int> > ed;
vector <int> z; // compression
vector <int> g[N];
int skip[N], par[N], dep[N], nchild[N];

struct data {
	int low; int cnt; int val;
	bool operator < (const data &other) const {
		return low < other.low;
	}
};
deque <data> dq[N]; // (lowest_depth, cnt, val)

void dfs(int u) {
	nchild[u] = 1;
	skip[u] = u;
	for (int &v : g[u]) {
		dep[v] = dep[u] + 1;
		par[v] = u;
		dfs(v);
		nchild[u] += nchild[v];
	}
}

void hld(int u) {
	for (int &v : g[u]) {
		if (nchild[v] * 2 >= nchild[u]) {
			skip[v] = skip[u];
		}
		hld(v);
	}
}

// -----------------------------------------------
// BIT
int T[N];
void upd(int x, int v) { for (; x < N; x += x & -x) T[x] += v; }
int get(int x) { int ret = 0; for (; x > 0; x -= x & -x) ret += T[x]; return ret; }

vector < pair<int,int> > buf;
long long calc_inv(int u) {
	long long ret = 0;

	while(u) {
		int root = skip[u];
		assert(dq[root].size() > 0);
		int pos = upper_bound(dq[root].begin(), dq[root].end(), data({dep[u], 0, 0})) - dq[root].begin() - 1;

		int curdep = dep[u];
		while(pos >= 0) {
			int curcnt = curdep - dq[root][pos].low + 1;
			// get
			ret += 1LL * curcnt * get(dq[root][pos].val);
			// update the current segment to BIT
			upd(dq[root][pos].val, curcnt);
			buf.push_back(make_pair(dq[root][pos].val, curcnt));
			// -> new position
			curdep = dq[root][pos].low - 1;
			--pos;
		}

		u = par[skip[u]];
	}

	// reset
	while(buf.size()) {
		int x = buf.back().first, v = buf.back().second;
		upd(x, -v);
		buf.pop_back();
	}

	return ret;
}

void add(int u) {
	//cerr << "ADD " << u << endl;
	int val = c[u];

	// climb up
	while(u) { // par[1] = 0
		int curdep = dep[u];
		int cnt = 0;
		while(dq[skip[u]].size() > 1 && dq[skip[u]][1].low <= curdep) {
			cnt += dq[skip[u]].front().cnt;
			dq[skip[u]].pop_front();
		}
		if (dq[skip[u]].size()) {
			cnt += curdep - dq[skip[u]][0].low + 1;
			dq[skip[u]][0].cnt -= curdep - dq[skip[u]][0].low + 1;
			dq[skip[u]][0].low = curdep + 1;
			if (dq[skip[u]][0].cnt <= 0) {
				dq[skip[u]].pop_front();
			}
		} else {
			cnt = 1;
		}

		dq[skip[u]].push_front({dep[skip[u]], cnt, val});
		u = par[skip[u]];
	}

	// for (int i = 1; i <= n; ++i) if (i == skip[i] && dq[i].size()) {
	// 	cerr << "dq " << i << endl;
	// 	for (auto &j : dq[i]) cerr << "low " << j.low << " cnt " << j.cnt << " val " << j.val << endl;
	// }
	// cerr << endl << endl;
}

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

	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> c[i];
		z.push_back(c[i]);
	}
	sort(z.begin(), z.end());
	z.erase(unique(z.begin(), z.end()), z.end());

	for (int i = 1; i <= n; ++i) {
		c[i] = lower_bound(z.begin(), z.end(), c[i]) - z.begin() + 1;
	}

	for (int i = 1; i < n; ++i) {
		int u, v; cin >> u >> v;
		ed.push_back(make_pair(u, v));
		g[u].push_back(v);
	}	

	// solve
	dfs(1);
	hld(1);
	// for (int i = 1; i <= n; ++i) {
	// 	cerr << i << ' ' << dep[i] << ' ' << skip[i] << endl;
	// }
	dq[1].push_back({0, 1, c[1]});

	for (auto &e : ed) {
		int u = e.first, v = e.second;
		printf("%lld\n", calc_inv(u));
		add(v);
	}
}

Compilation message

construction.cpp:18:12: error: template argument 1 is invalid
 deque <data> dq[N]; // (lowest_depth, cnt, val)
            ^
construction.cpp:18:12: error: template argument 2 is invalid
In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from construction.cpp:1:
construction.cpp: In function 'long long int calc_inv(int)':
construction.cpp:52:19: error: request for member 'size' in 'dq[root]', which is of non-class type 'int'
   assert(dq[root].size() > 0);
                   ^
construction.cpp:53:34: error: request for member 'begin' in 'dq[root]', which is of non-class type 'int'
   int pos = upper_bound(dq[root].begin(), dq[root].end(), data({dep[u], 0, 0})) - dq[root].begin() - 1;
                                  ^~~~~
construction.cpp:53:52: error: request for member 'end' in 'dq[root]', which is of non-class type 'int'
   int pos = upper_bound(dq[root].begin(), dq[root].end(), data({dep[u], 0, 0})) - dq[root].begin() - 1;
                                                    ^~~
construction.cpp:53:59: error: reference to 'data' is ambiguous
   int pos = upper_bound(dq[root].begin(), dq[root].end(), data({dep[u], 0, 0})) - dq[root].begin() - 1;
                                                           ^~~~
construction.cpp:12:8: note: candidates are: struct data
 struct data {
        ^~~~
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from construction.cpp:1:
/usr/include/c++/7/bits/range_access.h:318:5: note:                 template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)
     data(initializer_list<_Tp> __il) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:309:5: note:                 template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])
     data(_Tp (&__array)[_Nm]) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:299:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)
     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
/usr/include/c++/7/bits/range_access.h:289:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)
     data(_Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
construction.cpp:53:92: error: request for member 'begin' in 'dq[root]', which is of non-class type 'int'
   int pos = upper_bound(dq[root].begin(), dq[root].end(), data({dep[u], 0, 0})) - dq[root].begin() - 1;
                                                                                            ^~~~~
construction.cpp:57:38: error: invalid types 'int[int]' for array subscript
    int curcnt = curdep - dq[root][pos].low + 1;
                                      ^
construction.cpp:59:42: error: invalid types 'int[int]' for array subscript
    ret += 1LL * curcnt * get(dq[root][pos].val);
                                          ^
construction.cpp:61:20: error: invalid types 'int[int]' for array subscript
    upd(dq[root][pos].val, curcnt);
                    ^
construction.cpp:62:40: error: invalid types 'int[int]' for array subscript
    buf.push_back(make_pair(dq[root][pos].val, curcnt));
                                        ^
construction.cpp:64:25: error: invalid types 'int[int]' for array subscript
    curdep = dq[root][pos].low - 1;
                         ^
construction.cpp: In function 'void add(int)':
construction.cpp:89:21: error: request for member 'size' in 'dq[skip[u]]', which is of non-class type 'int'
   while(dq[skip[u]].size() > 1 && dq[skip[u]][1].low <= curdep) {
                     ^~~~
construction.cpp:89:48: error: invalid types 'int[int]' for array subscript
   while(dq[skip[u]].size() > 1 && dq[skip[u]][1].low <= curdep) {
                                                ^
construction.cpp:90:23: error: request for member 'front' in 'dq[skip[u]]', which is of non-class type 'int'
    cnt += dq[skip[u]].front().cnt;
                       ^~~~~
construction.cpp:91:16: error: request for member 'pop_front' in 'dq[skip[u]]', which is of non-class type 'int'
    dq[skip[u]].pop_front();
                ^~~~~~~~~
construction.cpp:93:19: error: request for member 'size' in 'dq[skip[u]]', which is of non-class type 'int'
   if (dq[skip[u]].size()) {
                   ^~~~
construction.cpp:94:33: error: invalid types 'int[int]' for array subscript
    cnt += curdep - dq[skip[u]][0].low + 1;
                                 ^
construction.cpp:95:17: error: invalid types 'int[int]' for array subscript
    dq[skip[u]][0].cnt -= curdep - dq[skip[u]][0].low + 1;
                 ^
construction.cpp:95:48: error: invalid types 'int[int]' for array subscript
    dq[skip[u]][0].cnt -= curdep - dq[skip[u]][0].low + 1;
                                                ^
construction.cpp:96:17: error: invalid types 'int[int]' for array subscript
    dq[skip[u]][0].low = curdep + 1;
                 ^
construction.cpp:97:21: error: invalid types 'int[int]' for array subscript
    if (dq[skip[u]][0].cnt <= 0) {
                     ^
construction.cpp:98:17: error: request for member 'pop_front' in 'dq[skip[u]]', which is of non-class type 'int'
     dq[skip[u]].pop_front();
                 ^~~~~~~~~
construction.cpp:104:15: error: request for member 'push_front' in 'dq[skip[u]]', which is of non-class type 'int'
   dq[skip[u]].push_front({dep[skip[u]], cnt, val});
               ^~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:142:8: error: request for member 'push_back' in 'dq[1]', which is of non-class type 'int'
  dq[1].push_back({0, 1, c[1]});
        ^~~~~~~~~