Submission #122848

#	Time	Username	Problem	Language	Result	Execution time	Memory
122848		onjo0127	Bulldozer (JOI17_bulldozer)	C++11	100 / 100	1969 ms	137892 KiB

bulldozer

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using pvi = pair<pii, int>;
#define X first
#define Y second
#pragma GCC optimize ("Ofast")

inline int CCW(pii A, pii B, pii C) {
	long long tmp = 1LL*A.X*B.Y + 1LL*B.X*C.Y + 1LL*C.X*A.Y - 1LL*B.X*A.Y - 1LL*C.X*B.Y - 1LL*A.X*C.Y;
	if(tmp < 0LL) return -1;
	if(tmp == 0LL) return 0;
	if(tmp > 0LL) return +1;
}

struct myp { int x, y; };
struct info { int x, y, v; };
struct node { long long ls, rs, mx, s; };
node operator +(node L, node R) {
	node ret;
	ret.s = L.s + R.s;
	ret.ls = max(L.ls, L.s + R.ls);
	ret.rs = max(R.rs, R.s + L.rs);
	ret.mx = max({L.mx, R.mx, L.rs + R.ls, ret.s});
	return ret;
}
bool operator <(myp P, myp Q) {
	return CCW({0, 0}, {P.x, P.y}, {Q.x, Q.y}) == -1;
}
const long long INF = 1LL * 1e18;
const node MINF = {0, 0, 0, -INF};

node T[8000];

struct segtree {
	node get(int idx, int s, int e, int l, int r) {
		if(r < s || e < l) return MINF;
		if(l <= s && e <= r) return T[idx];
		int m = s+e >> 1;
		return get(idx*2, s, m, l, r) + get(idx*2+1, m+1, e, l, r);
	}
	void upd(int idx, int s, int e, int p, int v) {
		if(p < s || e < p) return;
		if(s == e) {
			int x = max(0, v);
			T[idx] = {x, x, x, v};
			return;
		}
		int m = s+e >> 1;
		upd(idx*2, s, m, p, v);
		upd(idx*2+1, m+1, e, p, v);
		T[idx] = T[idx*2] + T[idx*2+1];
	}
};

inline int f(int x) { return max(x, -x); }

inline int CCW(info A, info B, info C) {
	return CCW((pii){A.x, A.y}, (pii){B.x, B.y}, (pii){C.x, C.y});
}

inline long long dst(pii A, pii B) {
	return 1LL * (A.X - B.X) * (A.X - B.X) + 1LL * (A.Y - B.Y) * (A.Y - B.Y);
}

vector<pvi> RQ;
vector<int> SS[2000009]; int cnt;
bool chk[2009][2009];
int O[2009], R[2009];
info A[2009];

int main() {
	int N; scanf("%d",&N);
	for(int i=1; i<=N; i++) {
		scanf("%d%d%d", &A[i].x, &A[i].y, &A[i].v);
	}

	for(int i=1; i<=N; i++) O[i] = i;
	sort(O+1, O+N+1, [&](int P, int Q) { return (pii){A[P].x, A[P].y} < (pii){A[Q].x, A[Q].y}; });
	for(int oi=1; oi<=N; oi++) {
		int i = O[oi];
		vector<int> T;
		for(int j=1; j<=N; j++) {
			int dx = A[j].x - A[i].x, dy = A[j].y - A[i].y;
			if(dx < 0 || (dx == 0 && dy <= 0)) continue;
			T.push_back(j);
		}
		sort(T.begin(), T.end(), [&](int P, int Q) {
			int ccw = CCW(A[i], A[P], A[Q]);
			if(ccw == 0) return dst({A[i].x, A[i].y}, {A[P].x, A[P].y}) < dst({A[i].x, A[i].y}, {A[Q].x, A[Q].y});
			return ccw == -1;
		});
		vector<int> P = {i}; int pr = -1, pdx = -1, pdy = -1;
		for(int j=0; j<T.size(); j++) {
			int it = T[j];
			int dx = A[it].x - A[i].x, dy = A[it].y - A[i].y;

			if(chk[i][it]) continue;
			if(pr == -1 || CCW(A[i], A[pr], A[it]) == 0) {
				P.push_back(it);
				pr = it;
			}
			else {
				RQ.push_back({{pdx, pdy}, cnt});
				SS[cnt++] = P;
				for(int p=0; p<P.size(); p++) for(int q=p+1; q<P.size(); q++) {
					chk[P[p]][P[q]] = 1;
				}
				P = {i, it};
				pr = it;
			}
			pdx = dx; pdy = dy;
		}
		if(pdx != -1) {
			RQ.push_back({{pdx, pdy}, cnt});
			SS[cnt++] = P;
			for(int p=0; p<P.size(); p++) for(int q=p+1; q<P.size(); q++) {
				chk[P[p]][P[q]] = 1;
			}
		}
	}
	segtree seg;
	long long ans = 0;
	for(int i=1; i<=N; i++) {
		int it = O[i];
		R[it] = i;
		seg.upd(1, 1, N, i, A[it].v);
	}

	ans = seg.get(1, 1, N, 1, N).mx;
	sort(RQ.begin(), RQ.end(), [&](pvi P, pvi Q) {
		int pdx, pdy; tie(pdx, pdy) = P.first;
		int qdx, qdy; tie(qdx, qdy) = Q.first;
		if((pdx == 0) != (qdx == 0)) return (pdx == 0) > (qdx == 0);
		return 1LL * pdy * qdx > 1LL * qdy * pdx;
	});

	long long pdx = 0, pdy = 0;
	for(auto& kt: RQ) {
		int dx, dy; tie(dx, dy) = kt.first;
		int K = SS[kt.second].size();
		for(int j=0; j<K; j++) seg.upd(1, 1, N, R[SS[kt.second][j]], A[SS[kt.second][K-j-1]].v);
		for(int j=0; j<(K>>1); j++) {
			swap(R[SS[kt.second][j]], R[SS[kt.second][K-j-1]]);
		}
		if(pdx && pdy && ((pdx == 0 && dx != 0) || pdy * dx != dy * pdx)) ans = max(ans, seg.get(1, 1, N, 1, N).mx);
		pdx = dx; pdy = dy;
	}
	printf("%lld", ans);
	return 0;
}

Compilation message (stderr)

bulldozer.cpp: In member function 'node segtree::get(int, int, int, int, int)':
bulldozer.cpp:39:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
bulldozer.cpp: In member function 'void segtree::upd(int, int, int, int, int)':
bulldozer.cpp:49:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:94:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<T.size(); j++) {
                ~^~~~~~~~~
bulldozer.cpp:106:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int p=0; p<P.size(); p++) for(int q=p+1; q<P.size(); q++) {
                  ~^~~~~~~~~
bulldozer.cpp:106:51: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int p=0; p<P.size(); p++) for(int q=p+1; q<P.size(); q++) {
                                                  ~^~~~~~~~~
bulldozer.cpp:117:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int p=0; p<P.size(); p++) for(int q=p+1; q<P.size(); q++) {
                 ~^~~~~~~~~
bulldozer.cpp:117:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int p=0; p<P.size(); p++) for(int q=p+1; q<P.size(); q++) {
                                                 ~^~~~~~~~~
bulldozer.cpp: In function 'int CCW(pii, pii, pii)':
bulldozer.cpp:14:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N; scanf("%d",&N);
         ~~~~~^~~~~~~~~
bulldozer.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &A[i].x, &A[i].y, &A[i].v);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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