Submission #395220

#	Time	Username	Problem	Language	Result	Execution time	Memory
395220		ChrisT	Bulldozer (JOI17_bulldozer)	C++17	80 / 100	2074 ms	82044 KiB

bulldozer

#include <bits/stdc++.h>
using namespace std;
const int MN = 2e3 + 5;
#define lc ind<<1
#define rc ind<<1|1
struct Node {
	long long mn,mx;
} tree[MN<<2];
void update (int ind, int tl, int tr, int i, long long v) {
	if (tl == tr) {
		tree[ind].mx = tree[ind].mn = v;
		return;
	}
	int mid = (tl + tr) / 2;
	if (i <= mid) update(lc,tl,mid,i,v);
	else update(rc,mid+1,tr,i,v);
	tree[ind].mn = min(tree[lc].mn,tree[rc].mn);
	tree[ind].mx = max(tree[lc].mx,tree[rc].mx);
}
long long queryMin (int ind, int tl, int tr, int l, int r) {
	if (tl > r || tr < l) return LLONG_MAX;
	if (l <= tl && tr <= r) return tree[ind].mn;
	int mid = (tl + tr) / 2;
	return min(queryMin(lc,tl,mid,l,r),queryMin(rc,mid+1,tr,l,r));
}
long long queryMax (int ind, int tl, int tr, int l, int r) {
	if (tl > r || tr < l) return LLONG_MIN;
	if (l <= tl && tr <= r) return tree[ind].mx;
	int mid = (tl + tr) / 2;
	return max(queryMax(lc,tl,mid,l,r),queryMax(rc,mid+1,tr,l,r));
}
int main () {
	int n,c=0; scanf ("%d",&n);
	vector<array<int,4>> pts(n); vector<int> pos(n), ow(n);
	vector<long long> vAt(n+1); vector<int> pAt(n+1);
	for (auto &[x,y,w,id] : pts) scanf ("%d %d %d",&x,&y,&w), id=c++, ow[id] = w;
	vector<tuple<int,int,long long,int,int>> events;
	for (int i = 0; i < n; i++) {
		for (int j = i+1; j < n; j++) {
			int dx = pts[i][0] - pts[j][0], dy = pts[i][1] - pts[j][1];
			if (dx < 0) dx = -dx, dy = -dy;
			if (dx == 0 && dy < 0) dy = -dy;
			events.push_back({dx,dy,(long long)dx * pts[i][1] - (long long)dy * pts[i][0],i,j});
		}
	}
	sort(pts.begin(),pts.end());
	auto cmp = [&] (const auto &a, const auto &b) {
		long long getA = (long long)get<1>(a) * get<0>(b), getB = (long long)get<1>(b) * get<0>(a);
		return getA > getB || (getA == getB && get<2>(a) < get<2>(b));
	};
	sort(events.begin(),events.end(),[&](const auto &a, const auto &b) {return cmp(a,b);});
	long long ret = 0, pre = 0;
	for (int i = 0; i < n; i++) {
		pos[pts[i][3]] = i+1; ret = max(ret,(long long)pts[i][2]);
		pre += pts[i][2]; vAt[i+1] = pre; pAt[i+1] = pts[i][3];
		update(1,1,n,i+1,pre);
	}
	vector<vector<array<int,2>>> cur;
	auto solve = [&] () {
		for (auto &v : cur) {
			int mn = 1e9, mx = -1e9;
			for (auto &[i,j] : v) mn = min({mn,pos[i],pos[j]}), mx = max({mx,pos[i],pos[j]});
			reverse(pAt.begin()+mn,pAt.begin()+mx+1);
			for (int i = mn; i <= mx; i++) {
				pos[pAt[i]] = i;
				vAt[i] = vAt[i-1] + ow[pAt[i]];
				update(1,1,n,i,vAt[i]);
			}
		}
		for (auto &v : cur) {
			int mn = 1e9, mx = -1e9;
			for (auto &[i,j] : v) mn = min({mn,pos[i],pos[j]}), mx = max({mx,pos[i],pos[j]});
			//go right
			long long get = queryMax(1,1,n,mx,n);
			for (int i = mx; i >= mn-1; i--) ret = max(ret,get - vAt[i]);
			//go left
			get = min(0LL,queryMin(1,1,n,1,mn-1));
			for (int i = mn-1; i <= mx; i++) ret = max(ret,vAt[i] - get);
			//go middle?
			long long best = vAt[mn-1];
			for (int i = mn; i <= mx; i++) {
				best = min(best,vAt[i]);
				ret = max(ret,vAt[i] - best);
			}
		}
	};
	for (int idx = 0; idx < (int)events.size(); idx++) {
		if (idx > 0 && (long long)get<1>(events[idx]) * get<0>(events[idx-1]) != (long long)get<0>(events[idx]) * get<1>(events[idx-1])) {
			solve();
			cur.clear();
		}
		if (!cur.empty() && cmp(events[idx],events[idx-1]) == cmp(events[idx-1],events[idx])) cur.back().push_back({get<3>(events[idx]),get<4>(events[idx])});
		else cur.push_back({{get<3>(events[idx]),get<4>(events[idx])}});
	}
	if (!cur.empty()) solve();
	//for (auto &[x,y,b,i,j] : events) {
	//	if (pos[i] > pos[j]) swap(i,j);
	//	ret = max(ret,vAt[pos[j]] - min(0LL,queryMin(1,1,n,1,pos[i]-1)) - min(0,ow[i]) - min(0,ow[j]));
	//	ret = max(ret,queryMax(1,1,n,pos[j],n) - (pos[i] == 1 ? 0LL : vAt[pos[i]-1]) - min(0,ow[i]) - min(0,ow[j]));
	//	update(1,1,n,pos[i],ow[j]-ow[i]); vAt[pos[i]] += ow[j] - ow[i];
	//	swap(pos[i],pos[j]);
	//}
	printf ("%lld\n",ret);
	return 0;
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:33:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |  int n,c=0; scanf ("%d",&n);
      |             ~~~~~~^~~~~~~~~
bulldozer.cpp:36:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |  for (auto &[x,y,w,id] : pts) scanf ("%d %d %d",&x,&y,&w), id=c++, ow[id] = w;
      |                               ~~~~~~^~~~~~~~~~~~~~~~~~~~~

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