Submission #104374

#	Time	Username	Problem	Language	Result	Execution time	Memory
104374		Noam527	Bulldozer (JOI17_bulldozer)	C++17	0 / 100	3 ms	512 KiB

bulldozer

#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 0;
const int OOO = 1;
using namespace std;

struct point {
	ll x, y, c;
	point() {}
	point(ll xx, ll yy, ll cc) {
		x = xx;
		y = yy;
		c = cc;
	}
	bool operator < (const point &a) const {
		if (y != a.y) return y < a.y;
		return x < a.x;
	}
};

struct block {
	ll mx, L, R, S;
	block(ll v = -inf) {
		mx = L = R = S = v;
	}
	block operator * (const block &a) const {
		block rtn;
		rtn.S = S + a.S;
		rtn.L = max(L, S + a.L);
		rtn.R = max(R + a.S, a.R);
		rtn.mx = max(max(mx, a.mx), R + a.L);
		return rtn;
	}
};

struct segtree {
	int n;
	vector<block> t;
	segtree() {}
	segtree(const vector<point> &a) {
		n = max(2, (int)a.size());
		while (n != (n & -n)) n += (n & -n);
		t.resize(2 * n);
		for (int i = 0; i < a.size(); i++)
			t[i + n - 1] = block(a[i].c);
		for (int i = n - 2; i >= 0; i--) fix(i);
	}
	void fix(int x) {
		t[x] = t[x + x + 1] * t[x + x + 2];
	}
	void upd(int x, ll v) {
		x += n - 1;
		t[x] = block(v);
		x = (x - 1) / 2;
		while (x) {
			fix(x);
			x = (x - 1) / 2;
		}
		fix(0);
	}
	ll query() {
		return t[0].mx;
	}
};

struct eve {
	ll x, y;
	int u, v;
	eve(ll xx = 0, ll yy = 0, int uu = 0, int vv = 0) {
		x = xx;
		y = yy;
		if (y < 0) {
			x = -x;
			y = -y;
		}
		u = uu;
		v = vv;
	}
	bool operator < (const eve &a) const {
		return x * a.y - y * a.x > 0;
	}
	bool operator == (const eve &a) const {
		return x * a.y == y * a.x;
	}
};

int n;
vector<point> a;
vector<int> ind;
vector<eve> E;
segtree T;

ll ans = 0;

void apply(int i, int j) {
	int u = ind[i], v = ind[j];
	if (OO) {
		cout << "swapping points\n";
		cout << a[u].x << " " << a[u].y << '\n';
		cout << a[v].x << " " << a[v].y << '\n';
		cout << "which is indicies " << u << " " << v << '\n';
	}
	swap(a[u], a[v]);
	swap(ind[i], ind[j]);
	T.upd(u, a[u].c);
	T.upd(v, a[v].c);
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	a.resize(n);
	E.reserve(n * (n - 1) / 2);
	for (auto &i : a) cin >> i.x >> i.y >> i.c;
	sort(a.begin(), a.end());
	ind.resize(n);
	for (int i = 0; i < n; i++) ind[i] = i;
	for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++)
		E.push_back(eve(a[j].x - a[i].x, a[j].y - a[i].y, i, j));
	sort(E.begin(), E.end());
	T = segtree(a);
	if (OO) {
		cout << "querying on\n";
		for (const auto &i : a) cout << i.x << " " << i.y << '\n';
		cout << "result = " << T.query() << '\n';
	}
	ans = max(ans, T.query());
	int nxt = 0;
	vector<pair<int, int>> those;
	while (nxt < E.size()) {
		those.clear();
		do {
			those.emplace_back(E[nxt].u, E[nxt].v);
			nxt++;
		} while (nxt < E.size() && E[nxt - 1] == E[nxt]);
		sort(those.begin(), those.end(), [](const pair<int, int> &aa, const pair<int, int> &bb) {
			if (ind[aa.first] != ind[bb.first]) return ind[aa.first] < ind[bb.first];
			return ind[aa.second] < ind[bb.second];
		});
		for (const auto &i : those) apply(i.first, i.second);

		if (OO) {
			cout << "querying on\n";
			for (const auto &i : a) cout << i.x << " " << i.y << '\n';
			cout << "result = " << T.query() << '\n';
		}
		ans = max(ans, T.query());
	}
	finish(ans);
}

Compilation message (stderr)

bulldozer.cpp: In constructor 'segtree::segtree(const std::vector<point>&)':
bulldozer.cpp:49:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a.size(); i++)
                   ~~^~~~~~~~~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:135:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (nxt < E.size()) {
         ~~~~^~~~~~~~~~
bulldozer.cpp:140:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   } while (nxt < E.size() && E[nxt - 1] == E[nxt]);
            ~~~~^~~~~~~~~~

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