Submission #204631

#	Time	Username	Problem	Language	Result	Execution time	Memory
204631		qwerty234	Aliens (IOI16_aliens)	C++14	4 / 100	50 ms	62328 KiB

aliens

#include "aliens.h"
 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define f first
#define se second
//#define int long long
#define pll pair<ll, ll>
#define pii pair<int, int>
 
 
using namespace std;
 
const int N = 3e5 + 123;
//const int N = 2e4 + 123;
const int M = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll inf = 1e16;
const ld INF = 1e13;
const ld maxR = 1e12 + 5;
 
 
struct segment {
	ll l, r, l1, r1;
	segment(ll l, ll r, ll l1, ll r1) : l(l), r(r), l1(l1), r1(r1) {};
};
 
 
struct line {
	ld b, k;
	ll cntid;
};
 
 
vector <line> lines;
 
 
ld intersect(line l1, line l2) {
	return (l1.b * 1.0 - l2.b * 1.0) / (l2.k * 1.0 - l1.k * 1.0);
}
 
 
ld val(line l, ld x) {
	return l.k * 1.0 * x + l.b;
}
 
ll vall(line l, ll x) {
	return l.k * x + l.b;
}
 
 
void addline(line a) {
	while (lines.size() > 1) {
		ld tmp = intersect(lines[lines.size() - 1], lines[lines.size() - 2]);
		if (val(lines[lines.size() - 1], tmp) > val(a, tmp))
			lines.pop_back();
		else
			break;
	}
	lines.pb(a);
}
 
 
pair<ld, ll> getmin(ll x) {
	ll L, R, M;
	pair<ld, ll> ans = {INF, inf};
	L = 0; R = lines.size() - 1;
	while (L <= R) {
		M = (L + R) / 2;
		ans = min(ans, {val(lines[M], x), lines[M].cntid});
		if (M == lines.size() - 1) {
			R = M - 1;
			continue;
		}
		if (make_pair(val(lines[M], x), lines[M].cntid) >= make_pair(val(lines[M + 1], x), lines[M + 1].cntid))
			L = M + 1;
		else
			R = M - 1;
	}
	return ans;
}
 
 
ll L[N], R[N], Lto[N], Rto[N], ar[N], sz = 0;
ll cntt[N];
bool isworth[N];
vector <segment> worth;
vector <ll> byl[N];
unordered_set <ll> st[M];
ld dp[N];
 
 
 
bool cmp(segment x, segment y) {
	return x.r < y.r;
}
 
 
ll cost(ll l, ll r) {
	if (l > r)
		return 0;
	return (r - l + 1) * (r - l + 1);
}
 
 
void add(int j) {
	line tmp;
	ld addd;
	if (j == 1 || worth[j].l > worth[j - 1].r)
		addd = 0.0;
	else
		addd = (ld)cost(worth[j].l, worth[j - 1].r);		
	tmp.b = dp[j - 1] + (ld)(worth[j].l) * (ld)(worth[j].l) - addd;
	tmp.k = -2.0 * ((ld)worth[j].l);
	tmp.cntid = cntt[j - 1];
	addline(tmp);
}
 
 
void count(ld costt, int n) {
	lines.clear();
	dp[0] = 0.0;
	cntt[0] = 0;
	for (int i = 1; i <= n; i++) {
//		cout << "segment " << i << " " << worth[i].l << " " << worth[i].r << endl;
		add(i);
		pair<ld, ll> tmpp = getmin((ld)(worth[i].r + 1));
		dp[i] = costt + tmpp.f + ((ld)(worth[i].r) + 1.0) * ((ld)(worth[i].r) + 1.0);
		cntt[i] = tmpp.se + 1;
//		cout << i << " " << dp[i] - costt * cntt[i] << endl;
	}
}
 
 
ll take_photos(int n, int m, int k, vector <int> r, vector <int> c) {
	int tmp = 0;
	for (int i = 0; i < n; i++) {
		if (c[i] >= r[i]) {
			if (st[r[i] + 1].count(c[i] + 1))
				continue;
			tmp++;
			L[tmp] = r[i] + 1;
			R[tmp] = c[i] + 1;
		} else {
			if (st[c[i] + 1].count(r[i] + 1))
				continue;
			tmp++;
			L[tmp] = c[i] + 1;
			R[tmp] = r[i] + 1;
		}
		st[L[tmp]].insert(R[tmp]);
		ar[++sz] = L[tmp];
		ar[++sz] = R[tmp];
	}
	n = tmp;
	sort(ar + 1, ar + sz + 1);
	ll t = unique(ar + 1, ar + sz + 1) - ar - 1;
	for (int i = 1; i <= n; i++) {
		Lto[i] = lower_bound(ar + 1, ar + t + 1, L[i]) - ar;		
		Rto[i] = lower_bound(ar + 1, ar + t + 1, R[i]) - ar;
		byl[Lto[i]].pb(i);
		isworth[i] = true;
	}
	ll curmax = 0;
	for (int i = 1; i <= 2 * n; i++) {
		ll localmx = 0;
		for (int to : byl[i]) {
			localmx = max(localmx, Rto[to]);
			if (Rto[to] <= curmax)
				isworth[to] = false;
		}
		for (int to : byl[i])
			if (Rto[to] < localmx)
				isworth[to] = false;
		curmax = max(curmax, localmx);
	}
	worth.pb({-1, -1, -1, -1});
	for (int i = 1; i <= n; i++) {
		if (isworth[i])
			worth.pb({L[i], R[i], Lto[i], Rto[i]});
	}
	n = worth.size() - 1;
	sort(worth.begin(), worth.end(), cmp);
	
//	count(1, n);
//	
//	cout << cntt[n] << " " << dp[n] - cntt[n] * 1 << endl;
//	
//	return 0;
	
	ld M, L = 0, R = maxR; //worth[worth.size() - 1].r * worth[worth.size() - 1].r;
	ll ans = inf;
	cout.precision(20);
	for (int i = 1; i <= 50; i++) {
		M = (L + R) / 2.0;
		if (M < 0)
			break;
		count(M, n);
		if (cntt[n] > k) {
			L = M + 1;
		} else {
			R = M - 1;
			ans = min(ans, (ll)(round((dp[n] - ((ld)cntt[n]) * M))));
//			if (ans == 9961190148) {
//				cout << M << " " << cntt[n] << endl;	
//			}
		}
	}
	return ans;
}
 
 
//main() {
//	ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
//	freopen("input.txt", "r", stdin);
//	int n, m, k; vector <int> r, c;
//	r.clear(); c.clear();
//	cin >> n >> m >> k;
//	for (int i = 1; i <= n; i++) {
//		int x, y;
//		cin >> x >> y;
////		cout << x << " " << y << endl;
//		r.pb(x);
//		c.pb(y);
//	}
//	cout << take_photos(n, m, k, r, c);
//	return 0;
//}

Compilation message (stderr)

aliens.cpp: In function 'std::pair<long double, long long int> getmin(long long int)':
aliens.cpp:73:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (M == lines.size() - 1) {
       ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40