oj.uz

Submission #502291

# Submission time Handle Problem Language Result Execution time Memory
502291 2022-01-05T17:42:15 Z flappybird Aliens (IOI16_aliens) C++14
0 / 100
 1 ms 300 KB 
#include "aliens.h"
#include <bits/stdc++.h>
#define MAX 101010
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
ll N, M, K;
vector<pll> arr;
ll S[MAX];
ll E[MAX];
bool cmp(pll a, pll b) {
	if (a.first == b.first) return a.second > b.second;
	else return a.first < b.first;
}
void trans(vector<pll>& v) {
	sort(v.begin(), v.end(), cmp);
	v.erase(unique(v.begin(), v.end()), v.end());
	N = v.size();
	ll i;
	for (i = 0; i < N; i++) {
		if (arr.empty()) arr.push_back(v[i]);
		else if (arr.back().first == v[i].first) continue;
		else if (arr.back().second >= v[i].second) continue;
		else arr.push_back(v[i]);
	}
	N = arr.size();
	for (i = 0; i < N; i++) S[i] = arr[i].first, E[i] = arr[i].second;
}
struct Line {
	ll a, b, num;
	Line(ll a, ll b, ll num) :a(a), b(b), num(num) {}
	Line() {}
	ll get(ll x) { return a * x + b; }
};
ll dp[MAX];
ll path[MAX];
vector<Line> linev;
void add(Line l) {
	if (linev.size() < 2) {
		linev.push_back(l);
		return;
	}
	while (linev.size() >= 2) {
		Line p1, p2;
		p1 = linev.back();
		linev.pop_back();
		p2 = linev.back();
		if ((p1.b - p2.b) * (l.a - p2.a) >= (l.b - p2.b) * (p1.a - p2.a)) {
			linev.push_back(p1);
			break;
		}
	}
	linev.push_back(l);
}
pll get(ll x) {
	ll l, r;
	l = 0;
	r = linev.size();
	ll i;
	while (r - l > 5) {
		ll mid = (l + r) / 2;
		Line l1, l2;
		l1 = linev[mid];
		l2 = linev[mid + 1];
		if (-(l1.b - l2.b) >= x * (l1.a - l2.a)) r = mid;
		else l = mid - 1;
	}
	ll mn = linev[l].get(x);
	ll mv = linev[l].num;
	for (i = l; i < r; i++) if (mn > linev[i].get(x)) mn = linev[i].get(x), mv = linev[i].num;
	return { mn, mv };
}
ll sq(ll x) {
	return x * x;
}
ll cht(ll lambda) {
	linev.clear();
	dp[0] = 2 * sq(E[0] - S[0] + 1) + lambda;
	add(Line(-4 * S[0], 2 * (sq(S[0]) - 2 * S[0] + 1), 0));
	ll i;
	for (i = 0; i < N; i++) path[i] = -1;
	for (i = 1; i < N; i++) {
		pll res = get(E[i]);
		dp[i] = res.first;
		dp[i] += 4 * E[i];
		dp[i] += 2 * sq(E[i]);
		path[i] = res.second;
		if (dp[i] > 2 * sq(E[i] - S[i] + 1) + dp[i - 1]) dp[i] = 2 * sq(E[i] - S[i] + 1) + dp[i - 1], path[i] = i;
		dp[i] += lambda;
		add(Line(-4 * S[i], dp[i - 1] + 2 * (sq(S[i]) - 2 * S[i] + 1), i));
	}
	ll v = N - 1;
	ll cnt = 0;
	while (v >= 0) {
		cnt++;
		v = path[v] - 1;
	}
	return cnt;
}
ll take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
	N = n;
	M = m;
	K = k;
	vector<pll> all;
	ll i;
	for (i = 0; i < N; i++) all.push_back(pll(r[i], c[i]));
	for (i = 0; i < N; i++) if (all[i].first > all[i].second) swap(all[i].first, all[i].second);
	trans(all);
	K = min(K, N);
	ll low, high;
	low = -1, high = 10000000000;
	while (high - low > 1) {
		ll mid = (low + high + 1) / 2;
		if (cht(mid) > K) low = mid;
		else high = mid;
	}
	cht(high);
	return (dp[N - 1] - K * high) / 2;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 4
2 Correct 0 ms 204 KB Correct answer: answer = 4
3 Correct 0 ms 300 KB Correct answer: answer = 4
4 Incorrect 1 ms 204 KB Wrong answer: output = 13, expected = 12
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Correct answer: answer = 1
2 Correct 1 ms 296 KB Correct answer: answer = 4
3 Correct 1 ms 204 KB Correct answer: answer = 1
4 Correct 0 ms 204 KB Correct answer: answer = 5
5 Correct 0 ms 288 KB Correct answer: answer = 41
6 Incorrect 0 ms 204 KB Wrong answer: output = 78145, expected = 71923
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 4
2 Correct 0 ms 204 KB Correct answer: answer = 4
3 Correct 0 ms 300 KB Correct answer: answer = 4
4 Incorrect 1 ms 204 KB Wrong answer: output = 13, expected = 12
5 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 4
2 Correct 0 ms 204 KB Correct answer: answer = 4
3 Correct 0 ms 300 KB Correct answer: answer = 4
4 Incorrect 1 ms 204 KB Wrong answer: output = 13, expected = 12
5 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 4
2 Correct 0 ms 204 KB Correct answer: answer = 4
3 Correct 0 ms 300 KB Correct answer: answer = 4
4 Incorrect 1 ms 204 KB Wrong answer: output = 13, expected = 12
5 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 4
2 Correct 0 ms 204 KB Correct answer: answer = 4
3 Correct 0 ms 300 KB Correct answer: answer = 4
4 Incorrect 1 ms 204 KB Wrong answer: output = 13, expected = 12
5 Halted 0 ms 0 KB -