Submission #428751

#	Time	Username	Problem	Language	Result	Execution time	Memory
428751		Kevin_Zhang_TW	Aliens (IOI16_aliens)	C++17	60 / 100	2033 ms	18696 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 100010, MAX_K = 17;
const ll inf = 1ll << 55;

#include "aliens.h"

ll sq(ll v) { return v * v; }

vector<int> allc;

void monolize(vector<int> &r, vector<int> &c, int &n) {
	for (int i = 0;i < n;++i) {
		if (r[i] > c[i]) swap(r[i], c[i]);
	}
	vector<pair<int,int>> loc;
	for (int i = 0;i < n;++i) loc.pb(c[i], r[i]);
	sort(AI(loc));
	int sz = 0;
	for (auto [x, y] : loc) {
		while (sz) {
			auto [xx, yy] = loc[sz-1];
			if (yy < y) break;
			--sz;
		}
		loc[sz++] = {x, y};
	}
	loc.resize(sz);

	r.clear(), c.clear();
	for (auto [x, y] : loc)
		r.pb(y), c.pb(x);
	n = r.size();
}

ll sp[MAX_K][MAX_N];

ll qry(int l, int r) {
	int lg = __lg(r-l);
	return min(sp[lg][l], sp[lg][r - (1<<lg)]);
}
void init_rmq(int g, vector<int> r, vector<int> c) {
	vector<int> allc(c); allc.pb(-1); sort(AI(allc)), allc.erase(unique(AI(allc)), end(allc));

	auto get_pos = [&](int c) -> int { 
		return lower_bound(AI(allc), c) - begin(allc);
	};

	fill(sp[0], sp[0] + g, inf);
	for (int i = 0;i < r.size();++i) {
		int j = get_pos(c[i]); 
		chmin(sp[0][j], (ll)r[i]);
		//chmin(omn[j], (ll)r[i]);
	}
	for (int d = 1;d < MAX_K;++d)
		for (int i = 0;i < g;++i) 
			sp[d][i] = min(sp[d-1][i], sp[d-1][ min(g-1, i + (1<<(d-1))) ]);
}
ll cost(int l, int i) {
	ll mnc = qry(l+1, i+1);
	ll wid = allc[i] - mnc + 1;
	ll rep = max<ll>(0, allc[l] - mnc + 1);
	return sq(wid) - sq(rep);
}

pair<ll,ll> get_dp(ll C, int g) {
	vector<ll> dp(g, inf); dp[0] = 0;
	vector<ll> cnt(g);

	deque<int> fr, ti;
	fr.pb(0), ti.pb(-1);

	for (int i = 1;i < g;++i) {
		if (ti.size() > 1 && ti[1] <= i)
			ti.pop_front(), fr.pop_front();

		auto trans = [&](int l, int i) {
			return cost(l, i) + dp[l];
		};

		dp[i] = C + trans(fr[0], i);
		cnt[i] = cnt[ fr[0] ] + 1;

		auto better = [&](int a, int b) {
			int l = i+1, r = g, mid;
			while (l < r) {
				mid = l + r >> 1;
				if (trans(a, mid) < trans(b, mid))
					r = mid;
				else
					l = mid+1;
			}
			return l;
		};

		int nt = better(i, fr.back());
		while (fr.size() > 1) {
			if (nt > ti.back()) break;
			fr.pop_back(), ti.pop_back();
			nt = better(i, fr.back());
		}
		fr.pb(i), ti.pb(nt);
	}

	return make_pair(cnt[g-1], dp[g-1]);
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {

	monolize(r, c, n);

	allc = c;
	allc.pb(-1); sort(AI(allc)), allc.erase(unique(AI(allc)), end(allc));

	int g = allc.size();

	init_rmq(g, r, c);

	ll L = 1, R = 1ll << 40, M;

	{
		auto [u, w] = get_dp(0, g);
		if (u <= k) return w;
	}

	while (L < R) {
		M = L + R >> 1;
		auto [u, w] = get_dp(M, g);
		if (u > k)
			L = M+1;
		else R = M;
	}
	auto [u, w] = get_dp(L, g);

	return w - L * k;
}

Compilation message (stderr)

aliens.cpp: In function 'void init_rmq(int, std::vector<int>, std::vector<int>)':
aliens.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for (int i = 0;i < r.size();++i) {
      |                 ~~^~~~~~~~~~
aliens.cpp: In lambda function:
aliens.cpp:102:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |     mid = l + r >> 1;
      |           ~~^~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:142:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  142 |   M = L + R >> 1;
      |       ~~^~~

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