oj.uz

Submission #122751

# Submission time Handle Problem Language Result Execution time Memory
122751 2019-06-29T08:33:21 Z 이온조(#2999) Bulldozer (JOI17_bulldozer) C++14
25 / 100
 2000 ms 137564 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using pvi = pair<pii, int>;
#define X first
#define Y second

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<vector<int> > SS;
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);
	}

	// int N = 2000;
	// srand(22315);
	// for(int i=1; i<=N; i++) {
	// 	A[i].x = rand();
	// 	A[i].y = rand();
	// 	A[i].v = rand();
	// }
	// set<pii> st;
	// for(int i=1 ;i<=N; i++) {
	// 	if(st.find({A[i].x, A[i].y}) != st.end()) return 0;
	// 	st.insert({A[i].x, A[i].y});
	// }
	// puts("start");

	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}, SS.size()});
				SS.push_back(P);
				for(int p=0; p<P.size(); p++) for(int q=p+1; q<P.size(); q++) {
					// printf("i: %d p: %d q: %d\n", i, p, q);
					chk[P[p]][P[q]] = 1;
				}
				P = {i, it};
				pr = it;
			}
			pdx = dx; pdy = dy;
		}
		if(pdx != -1) {
			RQ.push_back({{pdx, pdy}, SS.size()});
			SS.push_back(P);
			for(int p=0; p<P.size(); p++) for(int q=p+1; q<P.size(); q++) {
				// printf("i: %d p: %d q: %d\n", i, p, 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);
	}

	// puts("sort");

	// puts("O");
	// for(int i=1; i<=N; i++) printf("%d ",O[i]);
	// puts("");
	// printf("RQsize: %d\n", RQ.size());
	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;
	});

	// puts("calculate");

	int pdx = 0, pdy = 0;
	for(auto& kt: RQ) {
		vector<int> &it = SS[kt.second];

		// printf("it: ");
		// for(auto& jt: it) printf("%d ", jt);
		// puts("");
		int dx, dy; tie(dx, dy) = kt.first;
		
		int K = it.size();
		for(int j=0; j<K; j++) seg.upd(1, 1, N, R[it[j]], A[it[K-j-1]].v);
		for(int j=0; j<K/2; j++) {
			int p = it[j], q = it[K-j-1];
			swap(O[R[p]], O[R[q]]);
			swap(R[p], R[q]);
		}
		// puts("O");
		// for(int i=1; i<=N; i++) printf("%d ",O[i]);
		// puts("");

		if(pdx && pdy && ((pdx == 0 && dx != 0) || 1LL * pdy * dx != 1LL * dy * pdx)) {
			// printf("getans: %lld\n", seg.get(1, 1, N, 1, N).mx);
			ans = max(ans, seg.get(1, 1, N, 1, N).mx);
		}
		pdx = dx; pdy = dy;
	}
	printf("%lld", ans);
	return 0;
}

Compilation message

bulldozer.cpp: In member function 'node segtree::get(int, int, int, int, int)':
bulldozer.cpp:38: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:48:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:107:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<T.size(); j++) {
                ~^~~~~~~~~
bulldozer.cpp:119: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:119: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:131: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:131: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:13:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:72: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:74: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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 508 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 3 ms 380 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1016 KB Output is correct
2 Correct 5 ms 1016 KB Output is correct
3 Correct 5 ms 1020 KB Output is correct
4 Correct 5 ms 1016 KB Output is correct
5 Correct 6 ms 1004 KB Output is correct
6 Correct 5 ms 1016 KB Output is correct
7 Correct 5 ms 1016 KB Output is correct
8 Correct 5 ms 1016 KB Output is correct
9 Correct 5 ms 1016 KB Output is correct
10 Correct 6 ms 1016 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 6 ms 1016 KB Output is correct
22 Correct 5 ms 1016 KB Output is correct
23 Correct 6 ms 1144 KB Output is correct
24 Correct 6 ms 1016 KB Output is correct
25 Correct 6 ms 1016 KB Output is correct
26 Correct 5 ms 1016 KB Output is correct
27 Correct 6 ms 1016 KB Output is correct
28 Correct 5 ms 1016 KB Output is correct
29 Correct 6 ms 1016 KB Output is correct
30 Correct 7 ms 1016 KB Output is correct
31 Correct 5 ms 1016 KB Output is correct
32 Correct 5 ms 1016 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1016 KB Output is correct
2 Correct 5 ms 1016 KB Output is correct
3 Correct 5 ms 1020 KB Output is correct
4 Correct 5 ms 1016 KB Output is correct
5 Correct 6 ms 1004 KB Output is correct
6 Correct 5 ms 1016 KB Output is correct
7 Correct 5 ms 1016 KB Output is correct
8 Correct 5 ms 1016 KB Output is correct
9 Correct 5 ms 1016 KB Output is correct
10 Correct 6 ms 1016 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 6 ms 1016 KB Output is correct
22 Correct 5 ms 1016 KB Output is correct
23 Correct 6 ms 1144 KB Output is correct
24 Correct 6 ms 1016 KB Output is correct
25 Correct 6 ms 1016 KB Output is correct
26 Correct 5 ms 1016 KB Output is correct
27 Correct 6 ms 1016 KB Output is correct
28 Correct 5 ms 1016 KB Output is correct
29 Correct 6 ms 1016 KB Output is correct
30 Correct 7 ms 1016 KB Output is correct
31 Correct 5 ms 1016 KB Output is correct
32 Correct 5 ms 1016 KB Output is correct
33 Execution timed out 2057 ms 137564 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1016 KB Output is correct
2 Correct 5 ms 1016 KB Output is correct
3 Correct 5 ms 1020 KB Output is correct
4 Correct 5 ms 1016 KB Output is correct
5 Correct 6 ms 1004 KB Output is correct
6 Correct 5 ms 1016 KB Output is correct
7 Correct 5 ms 1016 KB Output is correct
8 Correct 5 ms 1016 KB Output is correct
9 Correct 5 ms 1016 KB Output is correct
10 Correct 6 ms 1016 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 6 ms 1016 KB Output is correct
22 Correct 5 ms 1016 KB Output is correct
23 Correct 6 ms 1144 KB Output is correct
24 Correct 6 ms 1016 KB Output is correct
25 Correct 6 ms 1016 KB Output is correct
26 Correct 5 ms 1016 KB Output is correct
27 Correct 6 ms 1016 KB Output is correct
28 Correct 5 ms 1016 KB Output is correct
29 Correct 6 ms 1016 KB Output is correct
30 Correct 7 ms 1016 KB Output is correct
31 Correct 5 ms 1016 KB Output is correct
32 Correct 5 ms 1016 KB Output is correct
33 Execution timed out 2057 ms 137564 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 508 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 3 ms 380 KB Output is correct
16 Correct 5 ms 1016 KB Output is correct
17 Correct 5 ms 1016 KB Output is correct
18 Correct 5 ms 1020 KB Output is correct
19 Correct 5 ms 1016 KB Output is correct
20 Correct 6 ms 1004 KB Output is correct
21 Correct 5 ms 1016 KB Output is correct
22 Correct 5 ms 1016 KB Output is correct
23 Correct 5 ms 1016 KB Output is correct
24 Correct 5 ms 1016 KB Output is correct
25 Correct 6 ms 1016 KB Output is correct
26 Correct 2 ms 256 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 2 ms 376 KB Output is correct
29 Correct 2 ms 376 KB Output is correct
30 Correct 2 ms 376 KB Output is correct
31 Correct 2 ms 376 KB Output is correct
32 Correct 2 ms 376 KB Output is correct
33 Correct 2 ms 376 KB Output is correct
34 Correct 2 ms 376 KB Output is correct
35 Correct 2 ms 376 KB Output is correct
36 Correct 6 ms 1016 KB Output is correct
37 Correct 5 ms 1016 KB Output is correct
38 Correct 6 ms 1144 KB Output is correct
39 Correct 6 ms 1016 KB Output is correct
40 Correct 6 ms 1016 KB Output is correct
41 Correct 5 ms 1016 KB Output is correct
42 Correct 6 ms 1016 KB Output is correct
43 Correct 5 ms 1016 KB Output is correct
44 Correct 6 ms 1016 KB Output is correct
45 Correct 7 ms 1016 KB Output is correct
46 Correct 5 ms 1016 KB Output is correct
47 Correct 5 ms 1016 KB Output is correct
48 Execution timed out 2057 ms 137564 KB Time limit exceeded
49 Halted 0 ms 0 KB -