Submission #984839

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
984839	2024-05-17T06:49:36 Z	pavement	Escape Route 2 (JOI24_escape2)	C++17	Compilation error	0 ms	0 KB

Main

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

using ii = pair<int, int>;
using ll = long long;

#define mp make_pair
#define pb push_back
#define eb emplace_back

int N, T, Q, _idx, M[100005], anc[25][100005];
ll dep[100005], min_width[100005];
vector<int> idx[100005];
vector<ii> V[100005];

ll f(int u, int k) {
	int v = u;
	for (int j = 20; j >= 0; j--) {
		if (k & (1 << j)) {
			v = anc[j][v];
		}
	}
	assert(v);
	return dep[u] - dep[v];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> T;
	for (int i = 1; i < N; i++) {
		cin >> M[i];
		min_width[i] = (ll)1e18;
		for (int j = 0, a, b; j < M[i]; j++) {
			cin >> a >> b;
			min_width[i] = min(min_width[i], b - a);
			V[i].eb(a, b);
			idx[i].pb(++_idx);
		}
		sort(V[i].begin(), V[i].end());
		for (int j = (int)V[i].size() - 1, sf = (int)2e9; j >= 0; j--) {
			sf = min(sf, V[i][j].second);
			V[i][j].second = sf;
		}
	}
	for (int i = N - 2; i >= 1; i--) {
		for (int j = 0; j < M[i]; j++) {
			int tmp = lower_bound(V[i + 1].begin(), V[i + 1].end(), mp(V[i][j].second, -1)) - V[i + 1].begin();
			ii potential_to = mp(V[i + 1][0].second + T - V[i][j].second, idx[i + 1][0]);
			if (tmp < (int)V[i + 1].size()) {
				potential_to = min(potential_to, mp(V[i + 1][tmp].second - V[i][j].second, idx[i + 1][tmp]));
			}
			anc[0][idx[i][j]] = potential_to.second;
			for (int k = 1; k <= 20; k++) {
				if (anc[k - 1][idx[i][j]] == 0) {
					break;
				}
				anc[k][idx[i][j]] = anc[k - 1][anc[k - 1][idx[i][j]]];
			}
			dep[idx[i][j]] = dep[potential_to.second] + potential_to.first;
		}
	}
	for (int i = 1; i < N; i++) {
		sort(idx[i].begin(), idx[i].end(), [&](const auto &lhs, const auto &rhs) {
			return V[i][lhs].second < V[i][rhs].second;
		});
		int mn = *min_element(idx[i].begin(), idx[i].end());
		vector<ii> copy_V(V[i].begin(), V[i].end());
		for (int j = 0; j < M[i]; j++) {
			V[i][j] = copy_V[idx[i][j] - mn];
		}
	}
	cin >> Q;
	for (int L, R; Q--; ) {
		cin >> L >> R;
		if (L + 1 == R) {
			cout << min_width[L] << '\n';
			continue;
		}
		int lo = 0, hi = M[L] - 1;
		//~ while (hi - lo >= 3) {
			//~ int m1 = lo + (hi - lo) / 3;
			//~ int m2 = hi - (hi - lo) / 3;
			//~ ll f1 = f(idx[L][m1], R - L - 1) + V[L][m1].second - V[L][m1].first;
			//~ ll f2 = f(idx[L][m2], R - L - 1) + V[L][m2].second - V[L][m2].first;
			//~ if (f1 < f2) {
				//~ hi = m2;
			//~ } else {
				//~ lo = m1;
			//~ }
		//~ }
		ll ans = (ll)1e18;
		for (int i = lo; i <= hi; i++) {
			ans = min(ans, f(idx[L][i], R - L - 1) + V[L][i].second - V[L][i].first);
		}
		cout << ans << '\n';
	}
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:36:42: error: no matching function for call to 'min(ll&, int)'
   36 |    min_width[i] = min(min_width[i], b - a);
      |                                          ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
Main.cpp:36:42: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   36 |    min_width[i] = min(min_width[i], b - a);
      |                                          ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
Main.cpp:36:42: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   36 |    min_width[i] = min(min_width[i], b - a);
      |                                          ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
Main.cpp:36:42: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   36 |    min_width[i] = min(min_width[i], b - a);
      |                                          ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
Main.cpp:36:42: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   36 |    min_width[i] = min(min_width[i], b - a);
      |                                          ^