oj.uz

Submission #448361

# Submission time Handle Problem Language Result Execution time Memory
448361 2021-07-29T20:18:57 Z dutch Food Court (JOI21_foodcourt) C++17
Compilation error
 0 ms 0 KB 
#include <bits/stdc++.h>
#define int int64_t
using namespace std;

template<class T> struct SegmentTree{
	T comb(T &x, T &y){
		if(x[0] + y[1] > y[0]){
			return {x[0] + y[1], x[1] + y[1], x[2]};
		}else{
			return {y[0], x[1] + y[1], y[2]};
		}
	}
	int n = 1, i; vector<T> a;
	SegmentTree(int N){ while((n+=n)<N); a.resize(2*n); }
	SegmentTree& operator[](int j){ i=j+n; return *this; }
	void operator=(int v){
		a[i] = {max(v, 0LL), v, i-n};
		while(i/=2) a[i] = comb(a[2*i], a[2*i+1]);
	}
	T operator()(int l, int r){
		T lx = {0, 0, 0}, rx = lx;
		for(l+=n, r+=n+1; l<r; l/=2, r/=2){
			if(l & 1) lx = comb(lx, a[l++]);
			if(r & 1) rx = comb(a[--r], rx);
		}
		return comb(lx, rx);
	}
};

struct FenwickTree{
	vector<int> a; int n;
	FenwickTree(int N) : a((n=N)+1) {}
	void add(int i, int v){
		for(++i; i<=n; i+=i&-i) a[i] += v;
	}
	int get(int i){
		int v = 0;
		for(++i; i>=1; i-=i&-i) v += a[i];
		return v;
	}
	int lower_bound(int v){
		int i = 0, j = 1<<19;
		while(j/=2)
			if(i+j<=n && a[i+j]<v) v -= a[i+=j];
		return i;
	}
};

const int LIM = 2.5e5+1;

int n, m, q, groupAt[LIM], ans[LIM];
array<int, 3> a[LIM];
vector<int> qL[LIM], qR[LIM], b[LIM];

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m >> q;
	for(int i=0, t; i<q; ++i){
		auto &[l, r, k] = a[i];
		cin >> t >> l >> r;
		if(t < 3){
			qL[l].push_back(i);
			qR[r].push_back(i);
		}
		if(t < 2){
			cin >> groupAt[i] >> k;
		}else if(t < 3){
			cin >> k; k = -k;
		}else{
			b[l].push_back(i);
			l = -1;
		}
	}

	SegmentTree<array<int, 3>> st(q);
	FenwickTree F(q);

	for(int i=1; i<=n; ++i){
		for(int &j : qR[i-1]){
			st[j] = 0;
			if(a[j][2] > 0) F.add(j,-a[j][2]);
		}
		for(int &j : qL[i]){
			st[j] = a[j][2];
			if(a[j][2] > 0) F.add(j, a[j][2]);
		}
		for(int &j : b[i]){
			auto v = st(0, j);
			if(v[0] >= a[j][1]){
				ans[j] = groupAt[F.lower_bound(F.get(j) - v[0] + a[j][1])];
			}
		}
	}
	for(int i=0; i<q; ++i){
		if(a[i][0] < 0) cout << ans[i] << '\n';
	}
}

Compilation message

foodcourt.cpp: In member function 'void SegmentTree<T>::operator=(int64_t)':
foodcourt.cpp:17:21: error: no matching function for call to 'max(int64_t&, long long int)'
   17 |   a[i] = {max(v, 0LL), v, i-n};
      |                     ^
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 foodcourt.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
foodcourt.cpp:17:21: note:   deduced conflicting types for parameter 'const _Tp' ('long int' and 'long long int')
   17 |   a[i] = {max(v, 0LL), v, i-n};
      |                     ^
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 foodcourt.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
foodcourt.cpp:17:21: note:   deduced conflicting types for parameter 'const _Tp' ('long int' and 'long long int')
   17 |   a[i] = {max(v, 0LL), v, i-n};
      |                     ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from foodcourt.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
foodcourt.cpp:17:21: note:   mismatched types 'std::initializer_list<_Tp>' and 'long int'
   17 |   a[i] = {max(v, 0LL), v, i-n};
      |                     ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from foodcourt.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
foodcourt.cpp:17:21: note:   mismatched types 'std::initializer_list<_Tp>' and 'long int'
   17 |   a[i] = {max(v, 0LL), v, i-n};
      |                     ^
foodcourt.cpp: In instantiation of 'void SegmentTree<T>::operator=(int64_t) [with T = std::array<long int, 3>; int64_t = long int]':
foodcourt.cpp:80:12:   required from here
foodcourt.cpp:17:8: error: no match for 'operator=' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<std::array<long int, 3> >, std::array<long int, 3> >::value_type' {aka 'std::array<long int, 3>'} and '<brace-enclosed initializer list>')
   17 |   a[i] = {max(v, 0LL), v, i-n};
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/tuple:39,
                 from /usr/include/c++/10/functional:54,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from foodcourt.cpp:1:
/usr/include/c++/10/array:94:12: note: candidate: 'constexpr std::array<long int, 3>& std::array<long int, 3>::operator=(const std::array<long int, 3>&)'
   94 |     struct array
      |            ^~~~~
/usr/include/c++/10/array:94:12: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const std::array<long int, 3>&'
/usr/include/c++/10/array:94:12: note: candidate: 'constexpr std::array<long int, 3>& std::array<long int, 3>::operator=(std::array<long int, 3>&&)'
/usr/include/c++/10/array:94:12: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::array<long int, 3>&&'