Submission #796683

# Submission time Handle Problem Language Result Execution time Memory
796683 2023-07-28T15:39:22 Z MetalPower Team Contest (JOI22_team) C++14
Compilation error
0 ms 0 KB
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define fi first
#define se second

const int MX = 150069;
const int INF = 1e9 + 7;

int N, arr[MX][3];
vector<int> cc[3];
vector<pii> ls[MX], cm;
set<pii> s;

struct segmax{
	int st[MX << 1];

	void build(){
		for(int i = 0; i < (MX << 1); i++) st[i] = -INF;
	}

	void upd(int p, int v){
		for(p += MX, st[p] = v, p >>= 1; p > 0; p >>= 1) st[p] = max(st[p << 1], st[p << 1|1]);
	}

	int que(int l, int r){
		int res = -INF;
		for(l += MX, r += MX + 1; l < r; l >>= 1, r >>= 1){
			if(l & 1) res = max(res, st[l++]);
			if(r & 1) res = max(res, st[--r]);
		}
		return res;
	}
} sx;

struct segmin{
	int st[MX << 1];

	void build(){
		for(int i = 0; i < (MX << 1); i++) st[i] = INF;
	}

	void upd(int p, int v){
		for(p += MX, st[p] = v, p >>= 1; p > 0; p >>= 1) st[p] = min(st[p << 1], st[p << 1|1]);
	}

	int que(int l, int r){
		int res = INF;
		for(l += MX, r += MX + 1; l < r; l >>= 1, r >>= 1){
			if(l & 1) res = min(res, st[l++]);
			if(r & 1) res = min(res, st[--r]);
		}
		return res;
	}
} sn;

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

	cin >> N;
	for(int i = 0; i < N; i++){
		for(int j = 0; j < 3; j++){
			cin >> arr[i][j];
			cc[j].push_back(arr[i][j]);
		}
	}

	for(int j = 0; j < 3; j++){
		sort(cc[j].begin(), cc[j].end());
		cc[j].resize(unique(cc[j].begin(), cc[j].end()) - cc[j].begin());
	}

	for(int i = 0; i < N; i++){
		for(int j = 0; j < 3; j++) arr[i][j] = lower_bound(cc[j].begin(), cc[j].end(), arr[i][j]) - cc[j].begin();
		ls[arr[i][0]].push_back({arr[i][1], arr[i][2]});
		cm.push_back({arr[i][1], arr[i][2]});
	}

	sort(cm.begin(), cm.end());
	cm.resize(unique(cm.begin(), cm.end()) - cm.begin());

	int mx = -1, ans = -1;
	bool f = false;

	sx.build();
	sn.build();

	set<pii> s;

	for(int i = 0; i < N; i++){
		
		for(pii x : ls[i]){ // query

			if(mx == -1) continue;

			int lf = sx.que(0, mx);
			int l = mx + 1, r = N - 1, rg = -1;
			while(l <= r){
				int mid = l + r >> 1, curr = sn.que(mid, r);
				if(curr < lf) rg = mid, l = mid + 1;
				else r = mid - 1;
			}

			if(cm[rg].fi > x.fi && lf > x.se) ans = max(ans, cc[0][i] + cc[1][cm[rg].fi] + cc[2][lf]); 
		}

		for(pii x : ls[i]){ // update

			int idx = lower_bound(cm.begin(), cm.end(), x) - cm.begin();

			s.insert(x);
			set<pii>::iterator it = s.find(x);

			{
				it++;
				if(it != s.end() && x.se > (*it).se) mx = max(mx, idx);
				it--;
				if(it != s.begin()){
					it--;
					if((*it).se > x.se) mx = max(mx, lower_bound(cm.begin(), cm.end(), (*it)) - cm.begin());
				}
			}

			sx.upd(idx, x.se);
			sn.upd(idx, x.se);
		}
	}

	cout << ans << '\n';
}

Compilation message

team.cpp: In function 'int main()':
team.cpp:100:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |     int mid = l + r >> 1, curr = sn.que(mid, r);
      |               ~~^~~
team.cpp:121:92: error: no matching function for call to 'max(int&, __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type)'
  121 |      if((*it).se > x.se) mx = max(mx, lower_bound(cm.begin(), cm.end(), (*it)) - cm.begin());
      |                                                                                            ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from team.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:
team.cpp:121:92: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'})
  121 |      if((*it).se > x.se) mx = max(mx, lower_bound(cm.begin(), cm.end(), (*it)) - cm.begin());
      |                                                                                            ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from team.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:
team.cpp:121:92: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'})
  121 |      if((*it).se > x.se) mx = max(mx, lower_bound(cm.begin(), cm.end(), (*it)) - cm.begin());
      |                                                                                            ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from team.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:
team.cpp:121:92: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  121 |      if((*it).se > x.se) mx = max(mx, lower_bound(cm.begin(), cm.end(), (*it)) - cm.begin());
      |                                                                                            ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from team.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:
team.cpp:121:92: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  121 |      if((*it).se > x.se) mx = max(mx, lower_bound(cm.begin(), cm.end(), (*it)) - cm.begin());
      |                                                                                            ^
team.cpp:84:7: warning: unused variable 'f' [-Wunused-variable]
   84 |  bool f = false;
      |       ^