oj.uz

Submission #53053

# Submission time Handle Problem Language Result Execution time Memory
53053 2018-06-27T20:19:01 Z kingpig9 Aliens (IOI16_aliens) C++11
0 / 100
 7 ms 4828 KB 
#include <bits/stdc++.h>
#include "aliens.h"

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5 + 10;
const int MAXM = 1e6 + 10;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

ll sqr (ll x) {
	return x * x;
}

template<class T>
void setmin (T &a, T b) {
	if (b < a) {
		a = b;
	}
}

template<class T>
void setmax (T &a, T b) {
	if (a < b) {
		a = b;
	}
}

int N, M, K;
int mxy[MAXM];
ll X[MAXN], Y[MAXN];

ll dp[MAXN];
int use[MAXN];
pii hull[MAXN];	//pii(start of interval, which index does it become optimal?)
int hl, hr;

ll getval (int a, int b) {
	ll newarea = sqr(Y[b] - X[a] + 1);
	if (a > 1) {
		newarea -= sqr(Y[a - 1] - X[a] + 1);
	}
	return dp[a - 1] + newarea;
}

void moo (ll cost) {
	hl = hr = 0;
	for (int i = 0; i <= N; i++) {
		if (i == 0) {
			dp[0] = 0;
			use[0] = 0;
			hull[hr++] = {1, 1};
		} else {
			while (hl < hr - 1 && hull[hl + 1].se <= i) {
				hl++;
			}
			
			int pind = hull[hl].se;
			use[i] = use[pind - 1] + 1;
			dp[i] = getval(pind, i) + cost;

			if (i == N) {
				break;
			}

			int optind = -1;
			while (hl != hr) {
				//when is getval(i + 1, ind) <= getval(hull.back().fi, ind)?
				int start1 = hull[hr - 1].fi;
				int start2 = i + 1;

				if (getval(start1, N) <= getval(start2, N)) {
					//optimization...
					optind = N + 1;
					break;
				}

				int lo = start2 - 1, hi = N + 1;	//hi is definitely true. lo is def not true
				while (hi - lo > 1) {
					int mid = (lo + hi) / 2;
					//only difference here: inequality needs to be strict -- that was the issue :P
					if (getval(start1, mid) > getval(start2, mid)) {
						hi = mid;
					} else {
						lo = mid;
					}
				}

				optind = hi;
				if (optind <= hull[hr - 1].se) {
					hr--;
				} else {
					break;
				}
			}

			if (optind <= N) {
				hull[hr++] = {i + 1, optind};
			}
		}
	}
}

ll take_photos (int nnn, int mmm, int kkk, vector<int> rrr, vector<int> ccc) {
	N = nnn;
	M = mmm;
	K = kkk;

	//R, C
	fillchar(mxy, -1);
	for (int i = 0; i < N; i++) {
		int x = rrr[i], y = ccc[i];
		if (x > y) {
			swap(x, y);
		}
		setmax(mxy[x], y);
	}

	N = 0;
	for (int x = 0; x < M; x++) {
		int y = mxy[x];
		if (y == -1) {
			continue;
		}

		if (N == 0 || Y[N] < y) {
			N++;
			X[N] = x;
			Y[N] = y;
		}
	}

	setmin(K, N);	//IMPORTANT!!! Note: N is adjusted. Therefore, it may not be true that K <= N -- need to do it again.
	ll lo = -1, hi = 2e12;

	while (hi - lo > 1) {
		ll mid = (lo + hi) / 2;
		moo(mid);
		if (use[N] > K) {
			lo = mid;
		} else {
			hi = mid;
		}
	}

	moo(hi);
	return dp[N] - hi * K;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4216 KB Correct answer: answer = 4
2 Correct 6 ms 4336 KB Correct answer: answer = 4
3 Correct 5 ms 4376 KB Correct answer: answer = 4
4 Correct 5 ms 4440 KB Correct answer: answer = 12
5 Correct 5 ms 4440 KB Correct answer: answer = 52
6 Correct 5 ms 4540 KB Correct answer: answer = 210
7 Correct 5 ms 4540 KB Correct answer: answer = 88
8 Correct 5 ms 4540 KB Correct answer: answer = 7696
9 Correct 5 ms 4540 KB Correct answer: answer = 1
10 Correct 4 ms 4540 KB Correct answer: answer = 2374
11 Correct 5 ms 4704 KB Correct answer: answer = 9502
12 Correct 5 ms 4704 KB Correct answer: answer = 49
13 Correct 5 ms 4704 KB Correct answer: answer = 151
14 Correct 5 ms 4704 KB Correct answer: answer = 7550
15 Correct 6 ms 4704 KB Correct answer: answer = 7220
16 Correct 6 ms 4704 KB Correct answer: answer = 7550
17 Correct 5 ms 4704 KB Correct answer: answer = 10000
18 Correct 6 ms 4704 KB Correct answer: answer = 10000
19 Incorrect 6 ms 4756 KB Wrong answer: output = 559, expected = 624
20 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4756 KB Correct answer: answer = 1
2 Correct 6 ms 4756 KB Correct answer: answer = 4
3 Correct 5 ms 4756 KB Correct answer: answer = 1
4 Correct 6 ms 4756 KB Correct answer: answer = 5
5 Incorrect 6 ms 4828 KB Wrong answer: output = 21, expected = 41
6 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4216 KB Correct answer: answer = 4
2 Correct 6 ms 4336 KB Correct answer: answer = 4
3 Correct 5 ms 4376 KB Correct answer: answer = 4
4 Correct 5 ms 4440 KB Correct answer: answer = 12
5 Correct 5 ms 4440 KB Correct answer: answer = 52
6 Correct 5 ms 4540 KB Correct answer: answer = 210
7 Correct 5 ms 4540 KB Correct answer: answer = 88
8 Correct 5 ms 4540 KB Correct answer: answer = 7696
9 Correct 5 ms 4540 KB Correct answer: answer = 1
10 Correct 4 ms 4540 KB Correct answer: answer = 2374
11 Correct 5 ms 4704 KB Correct answer: answer = 9502
12 Correct 5 ms 4704 KB Correct answer: answer = 49
13 Correct 5 ms 4704 KB Correct answer: answer = 151
14 Correct 5 ms 4704 KB Correct answer: answer = 7550
15 Correct 6 ms 4704 KB Correct answer: answer = 7220
16 Correct 6 ms 4704 KB Correct answer: answer = 7550
17 Correct 5 ms 4704 KB Correct answer: answer = 10000
18 Correct 6 ms 4704 KB Correct answer: answer = 10000
19 Incorrect 6 ms 4756 KB Wrong answer: output = 559, expected = 624
20 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4216 KB Correct answer: answer = 4
2 Correct 6 ms 4336 KB Correct answer: answer = 4
3 Correct 5 ms 4376 KB Correct answer: answer = 4
4 Correct 5 ms 4440 KB Correct answer: answer = 12
5 Correct 5 ms 4440 KB Correct answer: answer = 52
6 Correct 5 ms 4540 KB Correct answer: answer = 210
7 Correct 5 ms 4540 KB Correct answer: answer = 88
8 Correct 5 ms 4540 KB Correct answer: answer = 7696
9 Correct 5 ms 4540 KB Correct answer: answer = 1
10 Correct 4 ms 4540 KB Correct answer: answer = 2374
11 Correct 5 ms 4704 KB Correct answer: answer = 9502
12 Correct 5 ms 4704 KB Correct answer: answer = 49
13 Correct 5 ms 4704 KB Correct answer: answer = 151
14 Correct 5 ms 4704 KB Correct answer: answer = 7550
15 Correct 6 ms 4704 KB Correct answer: answer = 7220
16 Correct 6 ms 4704 KB Correct answer: answer = 7550
17 Correct 5 ms 4704 KB Correct answer: answer = 10000
18 Correct 6 ms 4704 KB Correct answer: answer = 10000
19 Incorrect 6 ms 4756 KB Wrong answer: output = 559, expected = 624
20 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4216 KB Correct answer: answer = 4
2 Correct 6 ms 4336 KB Correct answer: answer = 4
3 Correct 5 ms 4376 KB Correct answer: answer = 4
4 Correct 5 ms 4440 KB Correct answer: answer = 12
5 Correct 5 ms 4440 KB Correct answer: answer = 52
6 Correct 5 ms 4540 KB Correct answer: answer = 210
7 Correct 5 ms 4540 KB Correct answer: answer = 88
8 Correct 5 ms 4540 KB Correct answer: answer = 7696
9 Correct 5 ms 4540 KB Correct answer: answer = 1
10 Correct 4 ms 4540 KB Correct answer: answer = 2374
11 Correct 5 ms 4704 KB Correct answer: answer = 9502
12 Correct 5 ms 4704 KB Correct answer: answer = 49
13 Correct 5 ms 4704 KB Correct answer: answer = 151
14 Correct 5 ms 4704 KB Correct answer: answer = 7550
15 Correct 6 ms 4704 KB Correct answer: answer = 7220
16 Correct 6 ms 4704 KB Correct answer: answer = 7550
17 Correct 5 ms 4704 KB Correct answer: answer = 10000
18 Correct 6 ms 4704 KB Correct answer: answer = 10000
19 Incorrect 6 ms 4756 KB Wrong answer: output = 559, expected = 624
20 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4216 KB Correct answer: answer = 4
2 Correct 6 ms 4336 KB Correct answer: answer = 4
3 Correct 5 ms 4376 KB Correct answer: answer = 4
4 Correct 5 ms 4440 KB Correct answer: answer = 12
5 Correct 5 ms 4440 KB Correct answer: answer = 52
6 Correct 5 ms 4540 KB Correct answer: answer = 210
7 Correct 5 ms 4540 KB Correct answer: answer = 88
8 Correct 5 ms 4540 KB Correct answer: answer = 7696
9 Correct 5 ms 4540 KB Correct answer: answer = 1
10 Correct 4 ms 4540 KB Correct answer: answer = 2374
11 Correct 5 ms 4704 KB Correct answer: answer = 9502
12 Correct 5 ms 4704 KB Correct answer: answer = 49
13 Correct 5 ms 4704 KB Correct answer: answer = 151
14 Correct 5 ms 4704 KB Correct answer: answer = 7550
15 Correct 6 ms 4704 KB Correct answer: answer = 7220
16 Correct 6 ms 4704 KB Correct answer: answer = 7550
17 Correct 5 ms 4704 KB Correct answer: answer = 10000
18 Correct 6 ms 4704 KB Correct answer: answer = 10000
19 Incorrect 6 ms 4756 KB Wrong answer: output = 559, expected = 624
20 Halted 0 ms 0 KB -