Submission #676908

#	Time	Username	Problem	Language	Result	Execution time	Memory
676908		ymm	Bulldozer (JOI17_bulldozer)	C++17	25 / 100	2021 ms	99276 KiB

bulldozer

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

class Seg {
private:
	int sz;
	struct node {
		ll val, pre, suf, tot;
	} *t;

	void merge(int i) {
		node &l = t[2*i+1], &r = t[2*i+2];
		t[i].tot = l.tot + r.tot;
		t[i].pre = max(l.pre, l.tot + r.pre);
		t[i].suf = max(r.suf, r.tot + l.suf);
		t[i].val = max({l.val, r.val, l.suf + r.pre});
	}
	void up_impl(int p, ll x, int i, int b, int e) {
		if (e-b == 1) {
			ll y = max(x, 0ll);
			t[i] = {y, y, y, x};
			return;
		}
		if (p < (b+e)/2)
			up_impl(p, x, 2*i+1, b, (b+e)/2);
		else
			up_impl(p, x, 2*i+2, (b+e)/2, e);
		merge(i);
	}
public:
	void init(int n) {
		sz = n;
		t = new node[4*n]{};
	}
	void up(int p, ll x) { up_impl(p, x, 0, 0, sz); }
	ll get_max() { return t[0].val; }
} seg;

const int N = 2048;
int pos[N];
int ord[N];
ll val[N];

void swap_pnt_pos(int x, int y)
{
	int i = ord[x];
	int j = ord[y];
	seg.up(pos[i], val[j]);
	seg.up(pos[j], val[i]);
	swap(pos[i], pos[j]);
	swap(ord[x], ord[y]);
}

struct Angle {
	ll x, y;
};
int reg(const Angle &a)
{
	if (a.x > 0 && a.y == 0)
		return 0;
	if (a.x > 0 && a.y > 0)
		return 1;
	if (a.x == 0 && a.y > 0)
		return 2;
	if (a.x < 0 && a.y > 0)
		return 3;
	if (a.x < 0 && a.y == 0)
		return 4;
	if (a.x < 0 && a.y < 0)
		return 5;
	if (a.x == 0 && a.y < 0)
		return 6;
	if (a.x > 0 && a.y < 0)
		return 7;
	return -1;
}
ll sign(ll x) { return x < 0? -1: 1; }
bool operator<(const Angle &x, const Angle &y)
{
	int r1 = reg(x), r2 = reg(y);
	if (r1 != r2)
		return r1 < r2;
	if (r1%2 == 0)
		return 0;
	// x.y / x.x < y.y / y.x
	return x.y * y.x * sign(x.x * y.x) < y.y * x.x * sign(x.x * y.x);
}

pll pnt[N];

bool init_cmp_pnt(int i, int j)
{
	if (pnt[i].second != pnt[j].second)
		return pnt[i].second < pnt[j].second;
	else
		return pnt[i].first < pnt[j].first;
}

int n;

int is_left[N], is_done[N], id = 0;
vector<pair<Angle,pii>> vec;

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	Loop (i,0,n) {
		cin >> pnt[i].first >> pnt[i].second >> val[i];
		ord[i] = i;
	}
	sort(ord, ord+n, init_cmp_pnt);
	Loop (i,0,n)
		pos[ord[i]] = i;
	seg.init(n);
	Loop (i,0,n)
		seg.up(pos[i], val[i]);
	ll ans = seg.get_max();
	Loop (i,0,n) Loop (j,0,n) {
		if (i == j)
			continue;
		vec.push_back({{pnt[j].first - pnt[i].first, pnt[j].second - pnt[i].second}, {i, j}});
	}
	sort(vec.begin(), vec.end());
	for (int i = 0; i < vec.size(); ++i) {
		if (reg(vec[i].first) >= 4)
			break;
		int j = i;
		while (j < vec.size() && !(vec[i].first < vec[j].first))
			++j;
		++id;
		Loop (k,i,j) {
			auto [x, y] = vec[k].second;
			assert(pos[x] < pos[y]);
			is_left[pos[x]] = id;
		}
		Loop (k,i,j) {
			int l = pos[vec[k].second.first];
			if (is_done[l] == id)
				continue;
			if (is_left[l-1] == id)
				continue;
			int r = l+1;
			while (r < n && is_left[r-1] == id)
				++r;
			Loop (x,l,(l+r)/2)
				swap_pnt_pos(x, l+r-x-1);
			is_done[l] = id;
		}
		i = j-1;
		ans = max(ans, seg.get_max());
	}
	cout << ans << '\n';
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:130:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<Angle, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |  for (int i = 0; i < vec.size(); ++i) {
      |                  ~~^~~~~~~~~~~~
bulldozer.cpp:134:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<Angle, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |   while (j < vec.size() && !(vec[i].first < vec[j].first))
      |          ~~^~~~~~~~~~~~

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