Submission #1022336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022336		0npata	Bulldozer (JOI17_bulldozer)	C++17	Compilation error	0 ms	0 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

bulldozer

#include<bits/stdc++.h>
using namespace std;
 
 
#define float long double
#define int long long
 
const float PI = 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679;

const float EPSILON = 0.0000000000000000000000000000000000001;

#define vec vector
 
struct SegNode {
	int max_sss = 0;
	int max_pref_sum = 0;
	int max_suf_sum = 0;
	int sum = 0;
 
	SegNode merge(SegNode other) {
		return {max(max(max_sss, other.max_sss), max_suf_sum+other.max_pref_sum),
			max(max_pref_sum, sum+other.max_pref_sum),
			max(other.max_suf_sum, max_suf_sum + other.sum),
			sum + other.sum};
	}
};
 
struct SegTree {
	int n;
	vec<SegNode> data;
	SegTree(int in) {
		n = 1;
		while(n < in) n *= 2;
		data = vec<SegNode>(n*2);
	}
 
	void set(int i, int val) {
		i += n;
		data[i] = SegNode {max(val, 0LL), max(val, 0LL), max(val, 0LL), val};
		while(i > 1) {
			i /= 2;
			data[i] = data[i*2].merge(data[i*2+1]);
		}
	}
 
	SegNode query(int l, int r, int i = 1, int ll = 0, int rr = -1) {
		if(rr == -1) rr = n;
 
		if(ll >= r || rr <= l) return {};
		if(ll >= l && rr <= r) return data[i];
 
		int mid = (ll+rr)/2;
 
		return query(l, r, i*2, ll, mid).merge(query(l, r, i*2+1, mid, rr));
	}
};
 
struct Point {
	int x;
	int y;
	int w;
	int i;
 
};
 
float angle(Point p1, Point p2) {
	Point dif = {p2.x-p1.x, p2.y-p1.y};
	return atan2(dif.y, dif.x);
}
 
 
float norm_angle(float angle) {
	while(angle >= (float)2*PI) angle -= (float)2*PI;
	return angle;
}
 
int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
 
	int n;
	cin >> n;
 
	vec<Point> ps(n);
 
	for(int i = 0; i<n; i++) {
		cin >> ps[i].x >> ps[i].y >> ps[i].w;
	}
	auto comp_point = [](Point p1, Point p2) {
		return p1.x == p2.x ? p1.y < p2.y : p1.x < p2.x;
	};
 
 
	sort(ps.begin(), ps.end(), comp_point);
	for(int i = 0; i<n; i++) ps[i].i = i;
 
	vec<pair<float, pair<int, int>>> evs(0);
 
	for(int i = 0; i<n; i++) {
		for(int j = i+1; j<n; j++) {
			float cur_angle = angle(ps[i], ps[j]);
			//cerr << "ANGLE: " << cur_angle << '\n';
			float t1 = ((float)3)/2 * PI;
			float t2 = ((float)1)/2 * PI;
 
			float dif1 = (t1 + (float)2*PI) - cur_angle;
			float dif2 = (t2 + (float)2*PI) - cur_angle;
 
 
			dif1 = norm_angle(dif1);
			dif2 = norm_angle(dif2);
 
			// cerr << dif1 << ' ' << dif2 << '\n';
 
			evs.push_back({dif1, {i, j}});
			evs.push_back({dif2, {i, j}});
		}
	}
 
	sort(evs.begin(), evs.end(), [&](auto ev1, auto ev2) {
		if(abs(ev1.first - ev2.first) <= EPSILON {
			if(ev1.second.first == ev2.second.first) {
				return comp_point(ps[ev1.second.second], ps[ev2.second.second]);
			}
			else {
				return comp_point(ps[ev1.second.first], ps[ev2.second.first]);
			}
		}
		else {
			return ev1.first < ev2.first;
		}
	});
 
	//vec<int> ap(n);
 
	//iota(ap.begin(), ap.end(), 0);
 
	int ans = 0;
 
	SegTree st(n);
 
	for(int i = 0; i<n; i++) st.set(i, ps[i].w);
 
	auto eval = [&]() {
 
		int mx = st.query(0, n).max_sss;
		//cerr << mx << '\n';
		ans = max(mx, ans);
	};
 
	evs.push_back({1'000, {}});
 
 
 
 
	eval();
	for(int ei = 0; ei < evs.size()-1; ei++) {
		auto ev = evs[ei];
 
	        int i = ev.second.first;
		int j = ev.second.second;
		int temp = ps[i].i;
		ps[i].i = ps[j].i;
		ps[j].i = temp;
 
		//cerr << "swapping: " << i << ' ' << j << " at angle: " << ev.first <<  '\n';
 
		st.set(ps[i].i, ps[i].w);
		st.set(ps[j].i, ps[j].w);
 
		//swap(ap[ps[i].i], ap[ps[j].i]);
 
		if(abs(evs[ei+1].first - evs[ei].first) <= EPSILON) continue;
 
		eval();
	}
	//eval();
 
 
	cout << ans << '\n';
 
}

Compilation message (stderr)

bulldozer.cpp: In lambda function:
bulldozer.cpp:121:43: error: expected ')' before '{' token
  121 |   if(abs(ev1.first - ev2.first) <= EPSILON {
      |     ~                                     ^~
      |                                           )
bulldozer.cpp:132:2: error: expected primary-expression before '}' token
  132 |  });
      |  ^
bulldozer.cpp: In function 'int32_t main()':
bulldozer.cpp:157:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long double, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |  for(int ei = 0; ei < evs.size()-1; ei++) {
      |                  ~~~^~~~~~~~~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 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 bulldozer.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<std::pair<long double, std::pair<long long int, long long int> >*, std::vector<std::pair<long double, std::pair<long long int, long long int> > > >; _Iterator2 = __gnu_cxx::__normal_iterator<std::pair<long double, std::pair<long long int, long long int> >*, std::vector<std::pair<long double, std::pair<long long int, long long int> > > >; _Compare = main()::<lambda(auto:23, auto:24)>]':
/usr/include/c++/10/bits/stl_algo.h:82:17:   required from 'void std::__move_median_to_first(_Iterator, _Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = __gnu_cxx::__normal_iterator<std::pair<long double, std::pair<long long int, long long int> >*, std::vector<std::pair<long double, std::pair<long long int, long long int> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(auto:23, auto:24)> >]'
/usr/include/c++/10/bits/stl_algo.h:1924:34:   required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<long double, std::pair<long long int, long long int> >*, std::vector<std::pair<long double, std::pair<long long int, long long int> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(auto:23, auto:24)> >]'
/usr/include/c++/10/bits/stl_algo.h:1958:38:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<long double, std::pair<long long int, long long int> >*, std::vector<std::pair<long double, std::pair<long long int, long long int> > > >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(auto:23, auto:24)> >]'
/usr/include/c++/10/bits/stl_algo.h:1974:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<long double, std::pair<long long int, long long int> >*, std::vector<std::pair<long double, std::pair<long long int, long long int> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(auto:23, auto:24)> >]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::pair<long double, std::pair<long long int, long long int> >*, std::vector<std::pair<long double, std::pair<long long int, long long int> > > >; _Compare = main()::<lambda(auto:23, auto:24)>]'
bulldozer.cpp:132:3:   required from here
/usr/include/c++/10/bits/predefined_ops.h:156:30: error: void value not ignored as it ought to be
  156 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_comp_iter<_Compare>::operator()(_Value&, _Iterator) [with _Value = std::pair<long double, std::pair<long long int, long long int> >; _Iterator = __gnu_cxx::__normal_iterator<std::pair<long double, std::pair<long long int, long long int> >*, std::vector<std::pair<long double, std::pair<long long int, long long int> > > >; _Compare = main()::<lambda(auto:23, auto:24)>]':
/usr/include/c++/10/bits/stl_algo.h:1826:20:   required from 'void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<long double, std::pair<long long int, long long int> >*, std::vector<std::pair<long double, std::pair<long long int, long long int> > > >; _Compare = __gnu_cxx::__ops::_Val_comp_iter<main()::<lambda(auto:23, auto:24)> >]'
/usr/include/c++/10/bits/stl_algo.h:1854:36:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<long double, std::pair<long long int, long long int> >*, std::vector<std::pair<long double, std::pair<long long int, long long int> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(auto:23, auto:24)> >]'
/usr/include/c++/10/bits/stl_algo.h:1886:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<long double, std::pair<long long int, long long int> >*, std::vector<std::pair<long double, std::pair<long long int, long long int> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(auto:23, auto:24)> >]'
/usr/include/c++/10/bits/stl_algo.h:1977:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<long double, std::pair<long long int, long long int> >*, std::vector<std::pair<long double, std::pair<long long int, long long int> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(auto:23, auto:24)> >]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::pair<long double, std::pair<long long int, long long int> >*, std::vector<std::pair<long double, std::pair<long long int, long long int> > > >; _Compare = main()::<lambda(auto:23, auto:24)>]'
bulldozer.cpp:132:3:   required from here
/usr/include/c++/10/bits/predefined_ops.h:238:23: error: void value not ignored as it ought to be
  238 |  { return bool(_M_comp(__val, *__it)); }
      |                ~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<std::pair<long double, std::pair<long long int, long long int> >*, std::vector<std::pair<long double, std::pair<long long int, long long int> > > >; _Value = std::pair<long double, std::pair<long long int, long long int> >; _Compare = main()::<lambda(auto:23, auto:24)>]':
/usr/include/c++/10/bits/stl_heap.h:139:48:   required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<long double, std::pair<long long int, long long int> >*, std::vector<std::pair<long double, std::pair<long long int, long long int> > > >; _Distance = long int; _Tp = std::pair<long double, std::pair<long long int, long long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_val<main()::<lambda(auto:23, auto:24)> >]'
/usr/include/c++/10/bits/stl_heap.h:246:23:   required from 'void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<long double, std::pair<long long int, long long int> >*, std::vector<std::pair<long double, std::pair<long long int, long long int> > > >; _Distance = long int; _Tp = std::pair<long double, std::pair<long long int, long long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(auto:23, auto:24)> >]'
/usr/include/c++/10/bits/stl_heap.h:355:22:   required from 'void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<long double, std::pair<long long int, long long int> >*, std::vector<std::pair<long double, std::pair<long long int, long long int> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(auto:23, auto:24)> >]'
/usr/include/c++/10/bits/stl_algo.h:1666:23:   required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<long double, std::pair<long long int, long long int> >*, std::vector<std::pair<long double, std::pair<long long int, long long int> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(auto:23, auto:24)> >]'
/usr/include/c++/10/bits/stl_algo.h:1937:25:   required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<long double, std::pair<long long int, long long int> >*, std::vector<std::pair<long double, std::pair<long long int, long long int> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(auto:23, auto:24)> >]'
/usr/include/c++/10/bits/stl_algo.h:1953:27:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<long double, std::pair<long long int, long long int> >*, std::vector<std::pair<long double, std::pair<long long int, long long int> > > >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(auto:23, auto:24)> >]'
/usr/include/c++/10/bits/stl_algo.h:1974:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<long double, std::pair<long long int, long long int> >*, std::vector<std::pair<long double, std::pair<long long int, long long int> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(auto:23, auto:24)> >]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::pair<long double, std::pair<long long int, long long int> >*, std::vector<std::pair<long double, std::pair<long long int, long long int> > > >; _Compare = main()::<lambda(auto:23, auto:24)>]'
bulldozer.cpp:132:3:   required from here
/usr/include/c++/10/bits/predefined_ops.h:194:23: error: void value not ignored as it ought to be
  194 |  { return bool(_M_comp(*__it, __val)); }
      |                ~~~~~~~^~~~~~~~~~~~~~