Submission #446873

#	Time	Username	Problem	Language	Result	Execution time	Memory
446873		flappybird	Bulldozer (JOI17_bulldozer)	C++14	100 / 100	1985 ms	33584 KiB

bulldozer

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define MAX 101010
#define ln '\n'
struct Point {
	ll x, y;
	ll c;
	Point() :x(0), y(0) {}
	Point(ll x, ll y) :x(x), y(y) {}
	Point(ll x, ll y, ll c) :x(x), y(y), c(c) {}
};
bool operator<(const Point& p1, const Point& p2) {
	if (p1.x == p2.x) return p1.y < p2.y;
	return p1.x < p2.x;
}
bool operator==(const Point& p1, const Point& p2) {
	return p1.x == p2.x && p1.y == p2.y;
}
struct Node {
	ll lmx, rmx;
	ll sum, mx;
	Node(ll lmx, ll rmx, ll sum, ll mx) :lmx(lmx), rmx(rmx), sum(sum), mx(mx) {}
	Node() {
		lmx = rmx = mx = sum = 0;
	}
};
Node operator+(const Node& n1, const Node& n2) {
	Node ret;
	ret.lmx = max(n1.lmx, n1.sum + n2.lmx);
	ret.rmx = max(n2.rmx, n2.sum + n1.rmx);
	ret.sum = n1.sum + n2.sum;
	ret.mx = max(max(n1.mx, n2.mx), n1.rmx + n2.lmx);
	return ret;
}
struct segtree {
	vector<Node> tree;
	vector<ll> l, r;
	ll N, s;
	void init(ll x = 1) {
		if (x >= s) {
			l[x] = r[x] = x - s;
			return;
		}
		init(x * 2);
		init(x * 2 + 1);
		l[x] = l[x * 2];
		r[x] = r[x * 2 + 1];
		tree[x] = tree[x * 2] + tree[x * 2 + 1];
	}
	void update(ll x, ll v) {
		x += s;
		tree[x]= Node(max(0LL, v), max(0LL, v), v, max(0LL, v));
		x /= 2;
		while (x) {
			tree[x] = tree[x * 2] + tree[x * 2 + 1];
			x /= 2;
		}
	}
	ll maxall() {
		return tree[1].mx;
	}
	segtree(const vector<ll>& v) {
		N = v.size();
		s = 1LL << (ll)ceil(log2(N));
		l.resize(2 * s + 1);
		r.resize(2 * s + 1);
		tree.resize(2 * s + 1);
		ll i;
		for (i = 0; i < N; i++) tree[i + s] = Node(max(0LL, v[i]), max(0LL, v[i]), v[i], max(0LL, v[i]));
		init();
	}
	segtree() {}
};
vector<Point> point;
vector<pll> v;
vector<ll> val;
segtree seg;
bool cmp(const pll &p1, const pll &p2) {
	if ((point[p1.first].y - point[p1.second].y) * (point[p2.first].x - point[p2.second].x) == (point[p2.first].y - point[p2.second].y) * (point[p1.first].x - point[p1.second].x)) {
		if (point[p1.first] == point[p2.first]) return point[p1.second] < point[p2.second];
		return point[p1.first] < point[p2.first];
	}
	if (point[p1.first].y == point[p1.second].y) return (point[p2.first].y - point[p2.second].y) * (point[p2.first].x - point[p2.second].x) > 0;
	if (point[p2.first].y == point[p2.second].y) return (point[p1.first].y - point[p1.second].y) * (point[p1.first].x - point[p1.second].x) < 0;
	return (point[p1.first].y - point[p1.second].y) * (point[p2.first].x - point[p2.second].x) < (point[p2.first].y - point[p2.second].y) * (point[p1.first].x - point[p1.second].x);
}
bool eq(const pll& p1, const pll& p2) {
	return (point[p1.first].y - point[p1.second].y) * (point[p2.first].x - point[p2.second].x) == (point[p2.first].y - point[p2.second].y) * (point[p1.first].x - point[p1.second].x);
}
ll f(ll x) {
	if (!x) return 0;
	if (x > 0) return 1;
	else return -1;
}
ll ccw(Point p1, Point p2, Point p3) {
	return f((p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y));
}
ll N;
ll calc() {
	ll i, j;
	if (N == 1) {
		val[0] = max(val[0], 0LL);
		return val[0];
	}
	v.clear();
	for (i = 0; i < N; i++) {
		for (j = i + 1; j < N; j++) {
			if (point[i].x != point[j].x) {
				if (point[i].x < point[j].x) v.push_back({ i, j });
				else v.push_back({ j, i });
			}
		}
	}
	if (v.empty()) return 0;
	sort(v.begin(), v.end(), cmp);
	Point p1, p2;
	p1 = point[v[0].second];
	p2 = point[v[0].first];
	vector<ll> ord, rev;
	ord.resize(N);
	rev.resize(N);
	for (i = 0; i < N; i++) ord[i] = i;
	ll a, b, c;
	a = (p2.y - p1.y);
	b = (p2.x - p1.x);
	c = (p2.x * p1.y - p1.x * p2.y);
	for (i = 0; i < N; i++) {
		for (j = i + 1; j < N; j++) {
			ll x1, x2, y1, y2;
			x1 = point[ord[i]].x;
			x2 = point[ord[j]].x;
			y1 = point[ord[i]].y;
			y2 = point[ord[j]].y;
			ll c1 = (-ccw(p1, p2, point[ord[i]]) * abs(a * x1 - b * y1 + c));
			ll c2 = (-ccw(p1, p2, point[ord[j]]) * abs(a * x2 - b * y2 + c));
			if (c1 > c2) swap(ord[i], ord[j]);
			else if (c1 == c2) {
				if (a * b > 0) {
					if (x2 > x1) swap(ord[i], ord[j]);
				}
				else if (a * b == 0) {
					if (x2 < x1) swap(ord[i], ord[j]);
				}
				else {
					if (x2 < x1) swap(ord[i], ord[j]);
				}
			}
		}
	}
	for (i = 0; i < N; i++) rev[ord[i]] = i;
	vector<ll> nv;
	nv.resize(N);
	for (i = 0; i < N; i++) nv[i] = val[ord[i]];
	seg = segtree(nv);
	ll ans = 0;
	for (i = 0; i < v.size(); i++) {
		pll x = v[i];
		if ((i == 0) || (!eq(v[i], v[i - 1]))) ans = max(ans, seg.maxall());
		swap(ord[rev[x.first]], ord[rev[x.second]]);
		swap(rev[x.first], rev[x.second]);
		seg.update(rev[x.first], val[x.first]);
		seg.update(rev[x.second], val[x.second]);
	}
	return ans;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> N;
	ll i, j;
	for (i = 0; i < N; i++) {
		ll x, y, c;
		cin >> x >> y >> c;
		point.push_back(Point(x, y));
		val.push_back(c);
	}
	ll ans = 0;
	ans = calc();
	for (i = 0; i < N; i++) swap(point[i].x, point[i].y);
	ans = max(ans, calc());
	cout << ans << ln;
}

Compilation message (stderr)

bulldozer.cpp: In function 'll calc()':
bulldozer.cpp:162:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |  for (i = 0; i < v.size(); i++) {
      |              ~~^~~~~~~~~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:175:8: warning: unused variable 'j' [-Wunused-variable]
  175 |  ll i, j;
      |        ^

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