제출 #204670

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
204670		qwerty234	Aliens (IOI16_aliens)	C++14	100 / 100	690 ms	89696 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 = 1e17;
const ll 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 {
	ll 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<ll, ll> getmin(ll x) {
	ll L, R, M;
	pair<ll, ll> ans = {inf, inf};
	L = 0; R = lines.size() - 1;
	while (L <= R) {
		M = (L + R) / 2;
		ans = min(ans, {vall(lines[M], x), lines[M].cntid});
		if (M != lines.size() - 1)
			ans = min(ans, {vall(lines[M + 1], x), lines[M + 1].cntid});
		if (M != 0)
			ans = min(ans, {vall(lines[M - 1], x), lines[M - 1].cntid});
		if (M == lines.size() - 1) {
			R = M - 1;
			continue;
		}
		if (make_pair(vall(lines[M], x), lines[M].cntid) >= make_pair(vall(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];
ll 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;
	ll addd;
	if (j == 1 || worth[j].l > worth[j - 1].r)
		addd = 0ll;
	else
		addd = cost(worth[j].l, worth[j - 1].r);		
	tmp.b = dp[j - 1] + worth[j].l * worth[j].l - addd;
	tmp.k = -2 * worth[j].l;
	tmp.cntid = cntt[j - 1];
	addline(tmp);
}
 
 
pll count(ll costt, int n) {
	lines.clear();
	dp[0] = 0;
	cntt[0] = 0;
	for (int i = 1; i <= n; i++) {
		add(i);
		pair<ld, ll> tmpp = getmin(worth[i].r + 1);
		dp[i] = costt + tmpp.f + (worth[i].r + 1) * (worth[i].r + 1);
		cntt[i] = tmpp.se + 1;
	}
	return make_pair(dp[n] - cntt[n] * costt, cntt[n]);
}
 
 
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);
	
	k = min(n, k);
	
	
	ll M, L = 0, R = maxR;
	ll ans;
	pll val1, val2; ll p1, p2;
	while (L <= R) {
//		cout << L << " " << R << endl;
		M = (L + R) / 2;
		val1 = count(M, n);
		if (val1.se < k) {
			R = M - 1;
			continue;
		}
		val2 = count(M + 1, n);
		p2 = val2.se; p1 = val1.se;
		if (val2.se > k) {
			L = M + 1;
			continue;
		}
		if (p1 == k) {
			ans = val1.f;
			break;
		}
		if (p2 == k) {
			ans = val2.f;
			break;
		}
		ll dif = (val1.f - val2.f) / (p1 - p2);
		ans = val2.f + (k - p2) * dif;
		break;
	}
	
	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;
//}

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In function 'std::pair<long long int, 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)
       ~~^~~~~~~~~~~~~~~~~~~
aliens.cpp:77:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (M == lines.size() - 1) {
       ~~^~~~~~~~~~~~~~~~~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:223:9: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return ans;
         ^~~

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