Submission #614042

# Submission time Handle Problem Language Result Execution time Memory
614042 2022-07-30T17:21:30 Z amunduzbaev Two Antennas (JOI19_antennas) C++17
Compilation error
0 ms 0 KB
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
#define int ll
#define sow cerr<<"here"<<endl;

const int N = 2e5 + 5;
const int inf = 2e9;
struct ST{
	int tree[N << 2], mx[N << 2];
	int cost[N << 2];
	
	void push(int x, int lx, int rx){
		if(lx == rx) return;
		mx[x << 1] = max(mx[x << 1], mx[x]);
		mx[x << 1 | 1] = max(mx[x << 1 | 1], mx[x]);
		cost[x << 1] = max(cost[x << 1], mx[x << 1] - tree[x << 1]);
		cost[x << 1 | 1] = max(cost[x << 1 | 1], mx[x << 1 | 1] - tree[x << 1 | 1]);
		mx[x] = 0;
	}

	void set(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx){
			tree[x] = v, mx[x] = 0;
			cost[x] = -1;
			return;
		} int m = (lx + rx) >> 1;
		push(x, lx, rx);
		if(i <= m) set(i, v, lx, m, x << 1);
		else set(i, v, m + 1, rx, x << 1 | 1);
		tree[x] = min(tree[x << 1], tree[x << 1 | 1]);
		cost[x] = max(cost[x << 1], cost[x << 1 | 1]);
	}
		
	void add(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			mx[x] = max(mx[x], v);
			cost[x] = max(cost[x], mx[x] - tree[x]);
			return;
		} int m = (lx + rx) >> 1;
		add(l, r, v, lx, m, x << 1);
		add(l, r, v, m + 1, rx, x << 1 | 1);
		cost[x] = max(cost[x << 1], cost[x << 1 | 1]);
	}
	
	int get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return -inf;
		if(lx >= l && rx <= r) return cost[x];
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		return max(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
	}
	
	int get2(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return -inf;
		if(lx >= l && rx <= r){
			return mx[x];
		} int m = (lx + rx) >> 1;
		push(x, lx, rx);
		return max(get2(l, r, lx, m, x << 1), get2(l, r, m + 1, rx, x << 1 | 1));
	}
	
	int pos(int i, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) return tree[x];
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		if(i <= m) return pos(i, lx, m, x << 1);
		else return pos(i, m + 1, rx, x << 1 | 1);
	}
}tree; 

int h[N], a[N], b[N];
int l[N], r[N], res[N];
vector<ar<int, 2>> Q[N];
int n, q;

void solve(){
	vector<int> p(q); iota(p.begin(), p.end(), 0);
	sort(p.begin(), p.end(), [&](int i, int j){
		return r[i] < r[j];
	});
	
	for(int i=0;i<n;i++) tree.set(i, inf);
	
	int j = 0;
	for(int i=0;i<n;i++){
		for(auto [j, t] : Q[i]){
			if(t){
				tree.set(j, h[j]);
			} else {
				tree.set(j, inf);
			}
		} Q[i].clear();
		//~ for(int j=0;j<n;j++) cout<<tree.get2(j, j)<<" ";
		//~ cout<<"\n";
		//~ for(int j=0;j<n;j++) cout<<tree.get(j, j)<<" ";
		//~ cout<<"\n";
		//~ for(int j=0;j<n;j++) cout<<tree.pos(j)<<" ";
		//~ cout<<"\n";
		
		int L = max(i - b[i], 0ll), R = i - a[i];
		if(L <= R){
			//~ cout<<L<<" "<<R<<" "<<h[i]<<"\n";
			tree.add(L, R, h[i]);
		}
		
		Q[min(i + a[i], n)].push_back({i, 1});
		Q[min(i + b[i] + 1, n)].push_back({i, 0});
		
		while(j < q && r[p[j]] == i){
			res[p[j]] = max(res[p[j]], tree.get(l[p[j]], r[p[j]]));
			j++;
		}
	}
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	cin >> n;
	for(int i=0;i<n;i++) cin >> h[i] >> a[i] >> b[i];
	cin >> q;
	for(int i=0;i<q;i++){
		cin >> l[i] >> r[i];
		l[i]--, r[i]--;
	}
	memset(res, -1, sizeof res);
	solve();
	//~ for(int i=0;i<q;i++) cout<<res[i]<<"\n";
	//~ cout<<"\n";
	reverse(h, h + n);
	reverse(a, a + n);
	reverse(b, b + n);
	for(int i=0;i<q;i++) l[i] = n - l[i] - 1, r[i] = n - r[i] - 1, swap(l[i], r[i]);
	solve();
	for(int i=0;i<q;i++) cout<<res[i]<<"\n";
}

Compilation message

antennas.cpp: In function 'void solve()':
antennas.cpp:104:28: error: no matching function for call to 'max(ll, long long int)'
  104 |   int L = max(i - b[i], 0ll), R = i - a[i];
      |                            ^
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 antennas.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:
antennas.cpp:104:28: note:   deduced conflicting types for parameter 'const _Tp' ('long int' and 'long long int')
  104 |   int L = max(i - b[i], 0ll), R = i - a[i];
      |                            ^
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 antennas.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:
antennas.cpp:104:28: note:   deduced conflicting types for parameter 'const _Tp' ('long int' and 'long long int')
  104 |   int L = max(i - b[i], 0ll), R = i - a[i];
      |                            ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from antennas.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:
antennas.cpp:104:28: note:   mismatched types 'std::initializer_list<_Tp>' and 'long int'
  104 |   int L = max(i - b[i], 0ll), R = i - a[i];
      |                            ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from antennas.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:
antennas.cpp:104:28: note:   mismatched types 'std::initializer_list<_Tp>' and 'long int'
  104 |   int L = max(i - b[i], 0ll), R = i - a[i];
      |                            ^
antennas.cpp:105:11: error: 'R' was not declared in this scope
  105 |   if(L <= R){
      |           ^