Submission #1184656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184656		catch_me_if_you_can	Bulldozer (JOI17_bulldozer)	C++20	0 / 100	3 ms	1172 KiB

bulldozer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int MX = 2e3+5;
const int INF = 2e18;

struct ndata
{
	int L, R, S, T;
};

ndata create(int x)
{
	ndata ret;
	ret.L = ret.R = ret.S = max(x, 0ll);
	ret.T = x;
	return ret;
}

void rev(ndata &d)
{
	swap(d.L, d.R);
	return;
}

ndata merge(const ndata &d1, const ndata &d2)
{
	ndata d3;
	d3.L = max(d1.L, d1.T + d2.L);
	d3.R = max(d2.R, d2.T + d1.R);
	d3.S = max(max(d1.S, d2.S), d1.R + d2.L);
	d3.T = d1.T + d2.T;
	return d3;
}

struct seg_tree
{
	vector<ndata> tree;

	void build(const vector<int> &a, int id, int l, int r)
	{
		int m = (l+r)/2;
		if(l == r)
		{
			tree[id] = create(a[m]);
			return;
		}	
		build(a, 2*id, l, m);
		build(a, 2*id+1, m+1, r);
		tree[id] = merge(tree[2*id], tree[2*id+1]);
		return;
	}

	void init(int n, const vector<int> &a)
	{
		tree.resize(4*n+50);
		build(a, 1, 1, n);
		return;
	}

	void upd(int p, int val, int id, int l, int r)
	{
		if(l == r)
		{
			tree[id] = create(val);
			return;
		}
		int m = (l+r)/2;
		if(p <= m)
			upd(p, val, 2*id, l, m);
		else
			upd(p, val, 2*id+1, m+1, r);
		tree[id] = merge(tree[2*id], tree[2*id+1]);
		return;
	}

	ndata Q(int ql, int qr, int id, int l, int r)
	{
		if(qr < l || r < ql)
			return create(0);
		if((ql <= l) && (r <= qr))
			return tree[id];
		int m = (l+r)/2;
		ndata n1 = Q(ql, qr, 2*id, l, m);
		ndata n2 =  Q(ql, qr, 2*id+1, m+1, r);
		return merge(n1, n2);
	}
};

in sloppy(in pt1, in pt2)
{
	in zz = {pt1[1]-pt2[1], pt1[0]-pt2[0]};
	if(zz[1] < 0)
	{
		zz[1] = -zz[1];
		zz[0] = -zz[0];
	}
	if(zz[1] == 0)
		return {1, 0};
	int g = __gcd(abs(zz[1]), abs(zz[0]));
	zz[1]/=g;
	zz[0]/=g;
	return zz;
}

bool comp(array<int, 4> s1, array<int, 4> s2)
{
	int XX = s1[0]*s2[1];
	int YY = s2[0]*s1[1];
	if(XX < YY)
		return true;
	if(XX > YY)
		return false;
	return (((in){s1[2], s1[3]}) < ((in){s2[2], s2[3]}));
}

int dot(in x1, in x2)
{
	return x1[0]*x2[0] - x1[1]*x2[1];
}


vector<int> pa(MX, -1);

int leader(int u)
{
	if(pa[u] < 0)
		return u;
	else
		return pa[u] = leader(pa[u]);
}

void murder()
{
	cout << "0\n";
	exit(0);
	return;
}

vector<in> cmp[MX];

bool active[MX];

vector<int> stuff;
vector<in> Tt;
vector<in> MOON;
vector<int> Spl;

void MERGE(int u, int v)
{
	u = leader(u);
	v = leader(v);
	if(u == v)
		return;
	if(pa[u] < pa[v])
		swap(u, v);
	pa[v]+=pa[u];
	pa[u] = v;
	return;
}

signed main()
{
	fast();
	//murder();
	int n; cin >> n;
	vector<in> pt(n+1);
	vector<int> w(n+1);
	for(int i = 1; i <= n; i++)
		cin >> pt[i][0] >> pt[i][1] >> w[i];
	if(n == 1)
	{
		cout << max(w[1], 0ll) << "\n";
		return 0;	
	}
	vector<array<int, 4>> GG;
	for(int i = 1; i <= n; i++)
	{
		for(int j = i+1; j <= n; j++)
		{
			auto [x, y] = sloppy(pt[i], pt[j]);
			GG.pb({x, y, i, j});
		}
	}
	sort(GG.begin(), GG.end(), comp);
	//murder();
	vector<vector<in>> ff;
	in lst = {-1, -1};
	for(auto [x, y, i, j]: GG)
	{
		//cout << x << " " << y << endl;
		if(((in){x, y}) == lst)
			ff.back().pb({i, j});
		else
		{
			ff.pb({{i, j}});
			lst = {x, y};
		}
	}
	/*for(auto s: ff)
	{
		cout << "Next set: " << endl;
		for(auto [i, j]: s)
			cout << pt[i][0] << " "  << pt[i][1] << " " << pt[j][0] << " " << pt[j][1] << endl;
	}*/
	//murder();
	vector<int> where(n+1);
	vector<array<int, 3>> srt(n+1);
	for(int i = 1; i <= n; i++)
		srt[i] = {-pt[i][0], -pt[i][1], i};
	sort(srt.begin()+1, srt.end());
	vector<int> s(n+1);
	for(int i = 1; i <= n; i++)
	{
		s[i] = w[srt[i][2]];
		where[srt[i][2]] = i;
	}
	seg_tree work;
	work.init(n, s);
	int ANS = -INF;
	//cout << st[0] << " " << st[1] << endl;
	for(auto T: ff)
	{
		/*cout << "Current perm " << endl;
		vector<int> WTF(n+1);
		for(int i = 1; i <= n; i++)
			WTF[where[i]] = i;
		for(int i = 1; i <= n; i++)
			cout << WTF[i] << " ";
		cout << endl;*/
		stuff.clear();
		Tt.clear();
		Spl.clear();
		MOON.clear();
		for(auto [i, j]: T)
			pa[i] = pa[j] = -1;
		
		for(auto [i, j]: T)
		{
			if(!active[i])
			{
				stuff.pb(i);
				active[i] = 1;
			}
			if(!active[j])
			{
				stuff.pb(j);
				active[j] = 1;
			}
			MERGE(i, j);
		}
		for(auto [i, j]: T)
			active[i] = active[j] = 0;
		
		for(auto x: stuff)
		{
			int y = leader(x);
			cmp[y].pb({where[x], x});
			if(cmp[y].size() == 1)
				Spl.pb(y);
		}
		for(auto x: Spl)
		{
			sort(cmp[x].begin(), cmp[x].end());
			for(int i = 0; (2*i) < (cmp[x].size()-1); i++)
				Tt.pb({cmp[x][i][1], cmp[x][cmp[x].size()-1-i][1]});
			MOON.pb({cmp[x][0][0], cmp[x][cmp[x].size()-1][0]});
			cmp[x].clear();
		}

		for(auto [i, j]: Tt)
		{
			//cout << "Swapping i, j = " << i << ", " << j << endl;
			work.upd(where[i], w[j], 1, 1, n);
			work.upd(where[j], w[i], 1, 1, n);
			swap(where[i], where[j]);
			//assert(abs(where[i]-where[j]) == 1);
		}

		ndata curr = create(0);
		int lst = 1;
		sort(MOON.begin(), MOON.end());
		for(auto [l, r]: MOON)
		{
			if(l > lst)
				curr = merge(curr, work.Q(lst, l-1, 1, 1, n));
			curr = merge(curr, create(work.Q(l, r, 1, 1, n).T)); 
			lst = r+1;
		}
		if(n >= lst)
			curr = merge(curr, work.Q(lst, n, 1, 1, n));
		ANS = max(ANS, curr.S);
	}
	cout << ANS << "\n";
	return 0;
}	

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