Submission #26582

#	Time	Username	Problem	Language	Result	Execution time	Memory
26582		dwarn	Bulldozer (JOI17_bulldozer)	C++14	100 / 100	1209 ms	118008 KiB

bulldozer

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define rrep(i,a,b) for(int i = (b); i --> (a);)
#define all(v) (v).begin(),(v).end()
#define trav(x,v) for(auto &x : (v))
#define sz(v) (int)(v).size()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

struct ST {
	int n;
	vector<ll> sum, mx, mn, ans;
	ST(int _n) : n(_n){
		while(__builtin_popcount(n) > 1) ++n;
		sum.resize(2*n);
		mn.resize(2*n);
		mx.resize(2*n);
		ans.resize(2*n);
	}
	void upd(ll dif, int pos){
		for(pos += n; pos; pos /= 2){
			sum[pos] += dif;
			mn[pos] = min(0LL, sum[pos]);
			ans[pos] = mx[pos] = max(0LL, sum[pos]);
			if(pos < n){
				mn[pos] = min(mn[pos], min(mn[2*pos], sum[2*pos]+mn[2*pos+1]));
				mx[pos] = max(mx[pos], max(mx[2*pos], sum[2*pos]+mx[2*pos+1]));

				ans[pos] = max(ans[pos], max(ans[2*pos],ans[2*pos+1]));
				ans[pos] = max(ans[pos], mx[2*pos+1]+sum[2*pos]-mn[2*pos]);
			}
		}
	}
};

int ren[int(4e6)];
vector<vi> ls[int(2e6+10)];
int pos[int(2e6+10)], xs[2000], ys[2000], zs[2000];

int main(){
	rep(i,0,2e6+10) pos[i] = -1;

	int n;
	scanf("%d",&n);

	rep(i,0,n) scanf("%d %d %d",xs+i,ys+i,zs+i);

	auto vec = [&](int i, int j){
		int dx = xs[i]-xs[j], dy = ys[i]-ys[j];
		int g = dy==0 ? dx : __gcd(dx, dy);
		dx /= g, dy /= g;
		if(dx<0 || (dx==0 && dy<0)){
			dx = -dx, dy = -dy;
		}
		return pii(dx,dy);
	};

	vi perm(n);
	rep(i,0,n) perm[i] = i;
	sort(all(perm), [&](int i, int j){
		return xs[i]<xs[j]||(xs[i]==xs[j] && ys[i]<ys[j]);
	});
	vi mynum(n);
	rep(i,0,n) mynum[perm[i]] = i;

	vector<pair<pii,pii>> pas(n*(n-1)/2);
	int ix = 0;
	rep(i,0,n) rep(j,0,i) pas[ix++] = {vec(perm[i],perm[j]), {perm[i],perm[j]}};
	stable_sort(all(pas), [&](const pair<pii,pii> &a, const pair<pii,pii> &b){
		return (ll)a.first.second*b.first.first-(ll)a.first.first*b.first.second>0;
	});

	ST tree(n);
	rep(i,0,n)
		tree.upd(zs[i], mynum[i]);
	ll ans = tree.ans[1];

	for(int l = 0, r = 0; l < sz(pas); l = r){
		while(r < sz(pas) && pas[l].first == pas[r].first) ++r;
		rep(k,l,r){
			int a = pas[k].second.first, b = pas[k].second.second;
			tree.upd(zs[a]-zs[b], mynum[b]);
			tree.upd(zs[b]-zs[a], mynum[a]);
			swap(mynum[a], mynum[b]);
		}
		ans = max(ans, tree.ans[1]);
	}

	printf("%lld\n",ans);
	exit(0);

}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
bulldozer.cpp:48:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  rep(i,0,n) scanf("%d %d %d",xs+i,ys+i,zs+i);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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