Submission #1150866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150866		ZloyHR	Nile (IOI24_nile)	C++20	Compilation error	0 ms	0 KiB

nile

#include "nile.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<pll, ll> plll;
typedef pair<pll, pll> ppll;
typedef long double ld;
typedef tree<int,null_type,less<>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define V vector
#define fst first
#define snd second
#define ins insert
#define pb push_back
#define eb emplace_back
#define dbgs(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); --i)

template<typename T> void re(T &x) { cin >> x; }
template<typename T, typename ... U> void re(T &t, U &...u) { re(t); re(u...); }
template<typename T> void re(V<T> &x) { for(auto &a : x) re(a); }

template <typename T, typename V> ostream& operator<<(ostream& out, const pair<T, V> x) { out << "{" << x.fst << " : " << x.snd << "}"; return out; }
template <typename T> ostream& operator<<(ostream& out, const set<T> x) { for (auto& it : x) { out << it << " "; } return out; }
template <typename T> ostream& operator<<(ostream& out, const multiset<T> x) { for (auto& it : x) { out << it << " "; } return out; }
template <typename T, typename V> ostream& operator<<(ostream& out, const map<T, V> x) { for (auto& it : x) { out << "[" << it.fst << "]" << " = " << it.snd << "\n"; } return out; }
template <typename T> ostream& operator<<(ostream& out, const V<T> x) { if(!x.empty()) { for (int i = 0; i < x.size() - 1; ++i) { out << x[i] << " "; } out << x.back(); } return out; }
template <typename T> ostream& operator<<(ostream& out, const V<V<T>> x) { for (int i = 0; i < x.size() - 1; ++i) { out << "[" << i << "]" << " = {" << x[i] << "}\n"; } out << "[" << x.size() - 1 << "]" << " = {" << x.back() << "}\n"; return out; }
ostream& operator<<(ostream& out, const ordered_set x) { for (auto& it : x) { out << it << " "; } return out; }

template <class T, class U> inline void chmin(T& a, U&& b) { if (b < a) { a = b; } }
template <class T, class U> inline void chmax(T& a, U&& b) { if (a < b) { a = b; } }
template <class T, class U, class V> inline void clip(T& v, U&& lower, V&& upper) { if (v < lower) { v = lower; } else if (v > upper) { v = upper; } }

random_device dev;
mt19937 rng(dev());
//uniform_int_distribution<ll> dist(1,10);

const int N = 1e5 + 5;
int diff[N];
int weight[N];
struct DSU {
	V<ll> parent_size, a, b, mn, mx, mx1, mx2;
	V<ll> sum;
	V<set<pll>> wh;
	ll ans = 0;
	explicit DSU(const int n, V<int> &a, V<int> &b): parent_size(n, -1), sum(n, 0), mx1(n), mx2(n), wh(n), a(a), b(b), mn(n), mx(n) {
		FOR(i, 0, n) {
			mn[i] = mx[i] = i;
			mx1[i] = a[i] - b[i];
			mx2[i] = LLONG_MAX >> 4;
			wh[i].emplace(diff[i], i);
			sum[i] = b[i];
			ans += a[i];
		}
	}

	int calcAns(int idx) {
		if (-parent_size[idx] % 2 == 0) return 0;
		if (-parent_size[idx] % 4 == 1) return mx1[idx];
		return min(mx2[idx], min(a[mn[idx]] - b[mn[idx]], a[mx[idx]] - b[mx[idx]]));
	}

	int merge(int x, int y, int d) {
		x = leader(x), y = leader(y);
		if(-parent_size[x] < -parent_size[y]) swap(x, y);
		ans -= calcAns(x);
		ans -= sum[x];
		ans -= calcAns(y);
		ans -= sum[y];
		sum[x] += sum[y];
		parent_size[x] += parent_size[y];
		parent_size[y] = x;
		for (auto &it : wh[y]) wh[x].ins(it);
		while (!wh[x].empty()) {
			auto it = wh[x].begin();
			if (it->fst > d) break;
			chmin(mx2[x], a[it->snd] - b[it->snd]);
			wh[x].erase(it);
		}
		chmin(mx1[x], mx1[y]);
		if (weight[mn[x]] < weight[mn[y]]) mn[x] = mn[y]; else mx[x] = mx[y];
		ans += calcAns(x);
		ans += sum[x];
		return x;
	}
	int leader(const int x) {
		if(parent_size[x] < 0) return x;
		return parent_size[x] = leader(parent_size[x]);
	}
	int size(const int x) {
		return -parent_size[leader(x)];
	}
	bool isSame(const int x, const int y) {
		return leader(x) == leader(y);
	}
};

// Nile
V<ll> calculate_costs(V<int> W, V<int> A, V<int> B, V<int> E) {
	V<int> ordQuery(E.size()); iota(all(ordQuery), 0);
	sort(all(ordQuery), [&](int i, int j) { return E[i] < E[j]; });
	V<int> ordWeights(W.size()); iota(all(ordWeights), 0);
	sort(all(ordWeights), [&](int i, int j) { return W[i] < W[j]; });
	FOR(i, 1, W.size() - 1) {
		diff[i] = W[ordWeights[i + 1]] - W[ordWeights[i - 1]];
	}
	V<int> ordWeightPairs(W.size() - 1); iota(all(ordWeightPairs), 0);
	sort(all(ordWeightPairs), [&](int i, int j) { return (W[ordWeights[i + 1]] - W[ordWeights[i]]) < (W[ordWeights[j + 1]] - W[ordWeights[j]]); });
	DSU dsu(W.size(), A, B);
	int i = 0;
	V<ll> ans(E.size());
	for (auto &idx : ordQuery) {
		while (i < ordWeightPairs.size()) {
			int ordI = ordWeightPairs[i];
			if (W[ordWeights[ordI + 1]] - W[ordWeights[ordI]] <= E[idx]) {
				dsu.merge(ordWeights[ordI + 1], ordWeights[ordI], E[idx]);
				++i;
			} else break;
		}
		ans[idx] = dsu.ans;
	}
	return ans;
}

// int main() {
// 	int N;
// 	assert(1 == scanf("%d", &N));
// 	std::vector<int> W(N), A(N), B(N);
// 	for (int i = 0; i < N; i++)
// 		assert(3 == scanf("%d%d%d", &W[i], &A[i], &B[i]));
// 	int Q;
// 	assert(1 == scanf("%d", &Q));
// 	std::vector<int> E(Q);
// 	for (int j = 0; j < Q; j++)
// 		assert(1 == scanf("%d", &E[j]));
// 	fclose(stdin);
//
// 	std::vector<long long> R = calculate_costs(W, A, B, E);
//
// 	int S = (int)R.size();
// 	for (int j = 0; j < S; j++)
// 		printf("%lld\n", R[j]);
// 	fclose(stdout);
//
// 	return 0;
// }

Compilation message (stderr)

nile.cpp: In constructor 'DSU::DSU(int, std::vector<int>&, std::vector<int>&)':
nile.cpp:57:112: error: no matching function for call to 'std::vector<long long int>::vector(std::vector<int>&)'
   57 |         explicit DSU(const int n, V<int> &a, V<int> &b): parent_size(n, -1), sum(n, 0), mx1(n), mx2(n), wh(n), a(a), b(b), mn(n), mx(n) {
      |                                                                                                                ^~~~
In file included from /usr/include/c++/11/vector:67,
                 from nile.h:1,
                 from nile.cpp:1:
/usr/include/c++/11/bits/stl_vector.h:653:9: note: candidate: 'template<class _InputIterator, class> std::vector<_Tp, _Alloc>::vector(_InputIterator, _InputIterator, const allocator_type&) [with _InputIterator = _InputIterator; <template-parameter-2-2> = <template-parameter-1-2>; _Tp = long long int; _Alloc = std::allocator<long long int>]'
  653 |         vector(_InputIterator __first, _InputIterator __last,
      |         ^~~~~~
/usr/include/c++/11/bits/stl_vector.h:653:9: note:   template argument deduction/substitution failed:
nile.cpp:57:112: note:   candidate expects 3 arguments, 1 provided
   57 |         explicit DSU(const int n, V<int> &a, V<int> &b): parent_size(n, -1), sum(n, 0), mx1(n), mx2(n), wh(n), a(a), b(b), mn(n), mx(n) {
      |                                                                                                                ^~~~
In file included from /usr/include/c++/11/vector:67,
                 from nile.h:1,
                 from nile.cpp:1:
/usr/include/c++/11/bits/stl_vector.h:625:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::initializer_list<_Tp>, const allocator_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<long long int>]'
  625 |       vector(initializer_list<value_type> __l,
      |       ^~~~~~
/usr/include/c++/11/bits/stl_vector.h:625:43: note:   no known conversion for argument 1 from 'std::vector<int>' to 'std::initializer_list<long long int>'
  625 |       vector(initializer_list<value_type> __l,
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_vector.h:607:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>&&, const allocator_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<long long int>]'
  607 |       vector(vector&& __rv, const allocator_type& __m)
      |       ^~~~~~
/usr/include/c++/11/bits/stl_vector.h:607:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/11/bits/stl_vector.h:589:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>&&, const allocator_type&, std::false_type) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<long long int>; std::false_type = std::integral_constant<bool, false>]'
  589 |       vector(vector&& __rv, const allocator_type& __m, false_type)
      |       ^~~~~~
/usr/include/c++/11/bits/stl_vector.h:589:7: note:   candidate expects 3 arguments, 1 provided
/usr/include/c++/11/bits/stl_vector.h:585:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>&&, const allocator_type&, std::true_type) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<long long int>; std::true_type = std::integral_constant<bool, true>]'
  585 |       vector(vector&& __rv, const allocator_type& __m, true_type) noexcept
      |       ^~~~~~
/usr/include/c++/11/bits/stl_vector.h:585:7: note:   candidate expects 3 arguments, 1 provided
/usr/include/c++/11/bits/stl_vector.h:575:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(const std::vector<_Tp, _Alloc>&, const allocator_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<long long int>]'
  575 |       vector(const vector& __x, const allocator_type& __a)
      |       ^~~~~~
/usr/include/c++/11/bits/stl_vector.h:575:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/11/bits/stl_vector.h:572:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>&&) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
  572 |       vector(vector&&) noexcept = default;
      |       ^~~~~~
/usr/include/c++/11/bits/stl_vector.h:572:14: note:   no known conversion for argument 1 from 'std::vector<int>' to 'std::vector<long long int>&&'
  572 |       vector(vector&&) noexcept = default;
      |              ^~~~~~~~
/usr/include/c++/11/bits/stl_vector.h:553:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(const std::vector<_Tp, _Alloc>&) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
  553 |       vector(const vector& __x)
      |       ^~~~~~
/usr/include/c++/11/bits/stl_vector.h:553:28: note:   no known conversion for argument 1 from 'std::vector<int>' to 'const std::vector<long long int>&'
  553 |       vector(const vector& __x)
      |              ~~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_vector.h:522:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>::size_type, const value_type&, const allocator_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::value_type = long long int; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<long long int>]'
  522 |       vector(size_type __n, const value_type& __value,
      |       ^~~~~~
/usr/include/c++/11/bits/stl_vector.h:522:7: note:   candidate expects 3 arguments, 1 provided
/usr/include/c++/11/bits/stl_vector.h:510:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>::size_type, const allocator_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<long long int>]'
  510 |       vector(size_type __n, const allocator_type& __a = allocator_type())
      |       ^~~~~~
/usr/include/c++/11/bits/stl_vector.h:510:24: note:   no known conversion for argument 1 from 'std::vector<int>' to 'std::vector<long long int>::size_type' {aka 'long unsigned int'}
  510 |       vector(size_type __n, const allocator_type& __a = allocator_type())
      |              ~~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_vector.h:497:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(const allocator_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<long long int>]'
  497 |       vector(const allocator_type& __a) _GLIBCXX_NOEXCEPT
      |       ^~~~~~
/usr/include/c++/11/bits/stl_vector.h:497:36: note:   no known conversion for argument 1 from 'std::vector<int>' to 'const allocator_type&' {aka 'const std::allocator<long long int>&'}
  497 |       vector(const allocator_type& __a) _GLIBCXX_NOEXCEPT
      |              ~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_vector.h:487:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector() [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
  487 |       vector() = default;
      |       ^~~~~~
/usr/include/c++/11/bits/stl_vector.h:487:7: note:   candidate expects 0 arguments, 1 provided
nile.cpp:57:118: error: no matching function for call to 'std::vector<long long int>::vector(std::vector<int>&)'
   57 |         explicit DSU(const int n, V<int> &a, V<int> &b): parent_size(n, -1), sum(n, 0), mx1(n), mx2(n), wh(n), a(a), b(b), mn(n), mx(n) {
      |                                                                                                                      ^~~~
In file included from /usr/include/c++/11/vector:67,
                 from nile.h:1,
                 from nile.cpp:1:
/usr/include/c++/11/bits/stl_vector.h:653:9: note: candidate: 'template<class _InputIterator, class> std::vector<_Tp, _Alloc>::vector(_InputIterator, _InputIterator, const allocator_type&) [with _InputIterator = _InputIterator; <template-parameter-2-2> = <template-parameter-1-2>; _Tp = long long int; _Alloc = std::allocator<long long int>]'
  653 |         vector(_InputIterator __first, _InputIterator __last,
      |         ^~~~~~
/usr/include/c++/11/bits/stl_vector.h:653:9: note:   template argument deduction/substitution failed:
nile.cpp:57:118: note:   candidate expects 3 arguments, 1 provided
   57 |         explicit DSU(const int n, V<int> &a, V<int> &b): parent_size(n, -1), sum(n, 0), mx1(n), mx2(n), wh(n), a(a), b(b), mn(n), mx(n) {
      |                                                                                                                      ^~~~
In file included from /usr/include/c++/11/vector:67,
                 from nile.h:1,
                 from nile.cpp:1:
/usr/include/c++/11/bits/stl_vector.h:625:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::initializer_list<_Tp>, const allocator_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<long long int>]'
  625 |       vector(initializer_list<value_type> __l,
      |       ^~~~~~
/usr/include/c++/11/bits/stl_vector.h:625:43: note:   no known conversion for argument 1 from 'std::vector<int>' to 'std::initializer_list<long long int>'
  625 |       vector(initializer_list<value_type> __l,
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_vector.h:607:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>&&, const allocator_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<long long int>]'
  607 |       vector(vector&& __rv, const allocator_type& __m)
      |       ^~~~~~
/usr/include/c++/11/bits/stl_vector.h:607:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/11/bits/stl_vector.h:589:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>&&, const allocator_type&, std::false_type) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<long long int>; std::false_type = std::integral_constant<bool, false>]'
  589 |       vector(vector&& __rv, const allocator_type& __m, false_type)
      |       ^~~~~~
/usr/include/c++/11/bits/stl_vector.h:589:7: note:   candidate expects 3 arguments, 1 provided
/usr/include/c++/11/bits/stl_vector.h:585:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>&&, const allocator_type&, std::true_type) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<long long int>; std::true_type = std::integral_constant<bool, true>]'
  585 |       vector(vector&& __rv, const allocator_type& __m, true_type) noexcept
      |       ^~~~~~
/usr/include/c++/11/bits/stl_vector.h:585:7: note:   candidate expects 3 arguments, 1 provided
/usr/include/c++/11/bits/stl_vector.h:575:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(const std::vector<_Tp, _Alloc>&, const allocator_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<long long int>]'
  575 |       vector(const vector& __x, const allocator_type& __a)
      |       ^~~~~~
/usr/include/c++/11/bits/stl_vector.h:575:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/11/bits/stl_vector.h:572:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>&&) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
  572 |       vector(vector&&) noexcept = default;
      |       ^~~~~~
/usr/include/c++/11/bits/stl_vector.h:572:14: note:   no known conversion for argument 1 from 'std::vector<int>' to 'std::vector<long long int>&&'
  572 |       vector(vector&&) noexcept = default;
      |              ^~~~~~~~
/usr/include/c++/11/bits/stl_vector.h:553:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(const std::vector<_Tp, _Alloc>&) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
  553 |       vector(const vector& __x)
      |       ^~~~~~
/usr/include/c++/11/bits/stl_vector.h:553:28: note:   no known conversion for argument 1 from 'std::vector<int>' to 'const std::vector<long long int>&'
  553 |       vector(const vector& __x)
      |              ~~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_vector.h:522:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>::size_type, const value_type&, const allocator_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::value_type = long long int; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<long long int>]'
  522 |       vector(size_type __n, const value_type& __value,
      |       ^~~~~~
/usr/include/c++/11/bits/stl_vector.h:522:7: note:   candidate expects 3 arguments, 1 provided
/usr/include/c++/11/bits/stl_vector.h:510:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>::size_type, const allocator_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<long long int>]'
  510 |       vector(size_type __n, const allocator_type& __a = allocator_type())
      |       ^~~~~~
/usr/include/c++/11/bits/stl_vector.h:510:24: note:   no known conversion for argument 1 from 'std::vector<int>' to 'std::vector<long long int>::size_type' {aka 'long unsigned int'}
  510 |       vector(size_type __n, const allocator_type& __a = allocator_type())
      |              ~~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_vector.h:497:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(const allocator_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<long long int>]'
  497 |       vector(const allocator_type& __a) _GLIBCXX_NOEXCEPT
      |       ^~~~~~
/usr/include/c++/11/bits/stl_vector.h:497:36: note:   no known conversion for argument 1 from 'std::vector<int>' to 'const allocator_type&' {aka 'const std::allocator<long long int>&'}
  497 |       vector(const allocator_type& __a) _GLIBCXX_NOEXCEPT
      |              ~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_vector.h:487:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector() [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
  487 |       vector() = default;
      |       ^~~~~~
/usr/include/c++/11/bits/stl_vector.h:487:7: note:   candidate expects 0 arguments, 1 provided