Submission #1022361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022361		0npata	Bulldozer (JOI17_bulldozer)	C++17	80 / 100	1915 ms	131972 KiB

bulldozer

#include<bits/stdc++.h>
using namespace std;
 
 
#define float long double
#define int long long
 
const float PI = 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679;
 
 
#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(ev1.first - ev2.first == 0) {
			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(evs[ei+1].first - evs[ei].first == 0) continue;
 
		eval();
	}
	//eval();
 
 
	cout << ans << '\n';
 
}

Compilation message (stderr)

bulldozer.cpp: In function 'int32_t main()':
bulldozer.cpp:156: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]
  156 |  for(int ei = 0; ei < evs.size()-1; ei++) {
      |                  ~~~^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 35 / 35
• Subtask 4: 20 / 20
• Subtask 5: 0 / 20