Submission #395199

#	Time	Username	Problem	Language	Result	Execution time	Memory
395199		ChrisT	Bulldozer (JOI17_bulldozer)	C++17	20 / 100	2088 ms	33288 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,lz;
} tree[MN<<2];
void push_down (int ind, int l, int r) {
	if (tree[ind].lz) {
		tree[ind].mn += tree[ind].lz;
		tree[ind].mx += tree[ind].lz;
		if (l != r) {
			tree[lc].lz += tree[ind].lz;
			tree[rc].lz += tree[ind].lz;
		}
		tree[ind].lz = 0;
	}
}
void update (int ind, int tl, int tr, int l, int r, long long v) {
	push_down(ind,tl,tr);
	if (tl > r || tr < l) return;
	if (l <= tl && tr <= r) {
		tree[ind].lz += v;
		push_down(ind,tl,tr);
		return;
	}
	int mid = (tl + tr) / 2;
	update(lc,tl,mid,l,r,v); update(rc,mid+1,tr,l,r,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) {
	push_down(ind,tl,tr);
	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) {
	push_down(ind,tl,tr);
	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);
	for (auto &[x,y,w,id] : pts) scanf ("%d %d %d",&x,&y,&w), id=c++, ow[id] = w;
	vector<array<int,4>> 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,i,j});
		}
	}
	sort(pts.begin(),pts.end());
	sort(events.begin(),events.end(),[&](const auto &a, const auto &b) {return (long long)a[1] * b[0] > (long long)b[1] * a[0];});
	for (int i = 0; i < (int)events.size(); i++) {
		for (int j = i+1; j < (int)events.size(); j++) {
			assert((long long)events[i][0] * events[j][1] != (long long)events[j][0] * events[i][1]);
		}
	}
	long long ret = 0;
	for (int i = 0; i < n; i++) {
		pos[pts[i][3]] = i+1; ret = max(ret,(long long)pts[i][2]);
		update(1,1,n,i+1,n,pts[i][2]);
	}
	for (auto &[x,y,i,j] : events) {
		//printf ("order: ");
		//for (int i = 1; i <= n; i++) for (int j =0 ;j < n; j++) if (pos[j]==i) printf ("%d ",j);
		//printf ("\n");
		//for (int i = 1; i <= n; i++) printf ("%lld ",queryMax(1,1,n,i,i));
		//printf ("\n");
		if (pos[i] > pos[j]) swap(i,j);
		ret = max(ret,queryMax(1,1,n,pos[j],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 : queryMax(1,1,n,pos[i]-1,pos[i]-1)) - min(0,ow[i]) - min(0,ow[j]));
		update(1,1,n,pos[i],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:48:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |  int n,c=0; scanf ("%d",&n);
      |             ~~~~~~^~~~~~~~~
bulldozer.cpp:50:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |  for (auto &[x,y,w,id] : pts) scanf ("%d %d %d",&x,&y,&w), id=c++, ow[id] = w;
      |                               ~~~~~~^~~~~~~~~~~~~~~~~~~~~

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