Submission #1272674

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272674		RAG27	Aliens (IOI16_aliens)	C++20	4 / 100	1 ms	352 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto operator<<(auto&o, auto p)->decltype(p.first, o){return o << '(' << p.first << ", " << p.second << ')';}
auto operator<<(auto&o, auto x)->decltype(x.end(), o){o << '{';int i=2; for (auto e : x)o << (", ")+i << e, i=0; return o << '}';}
#define LOG(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X);
#else
#define LOG(X...)(void)0
#endif

void mn(int &a, int b) {
	a = min(a, b);
}


long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
	vector<int> row(m, INT_MAX), column(m, INT_MAX);
	for (int i = 0; i < n; i++) {
		mn(row[r[i]], c[i]);
		mn(column[c[i]], r[i]);
	}
	auto check = [&](long long lambda) -> pair<long long, int> {
		long long value = 0;
		stack<pair<int, int>> recs;
		for (int rc = 0; rc < m; rc++) {
			int mrc = min(column[rc], row[rc]);
			if (mrc > rc)
				continue;

			auto added = [&](pair<int, int> t, pair<int, int> a) -> long long {
				int size = t.second - t.first + 1;
				if (t.first > a.second)
					return (long long)size * size;
				int sizeDif = a.second - t.first + 1;
				return (long long)size * size - (long long)sizeDif * sizeDif;
				
			};
			while (!recs.empty() && recs.top().first >= mrc) {
				auto t = recs.top();
				recs.pop();
				value -= lambda;
				pair<int, int> last = {-1, -1};
				if (!recs.empty())
					last = recs.top();
				value -= added(t, last);
			}
			
			if (recs.empty()) {
				value += added({mrc, rc}, {-1, -1}) + lambda;
				recs.push({mrc, rc});
				continue;
			}

			auto t = recs.top();
			recs.pop();
			pair<int, int> last = {-1, -1};
			if (!recs.empty())
				last = recs.top();
			long long va = added({t.first, rc}, last) - added(t, last);
			long long vna = added({mrc, rc}, t) + lambda;
			if (vna < va) {
				value += vna;
				recs.push(t);
				recs.push({mrc, rc});
			} else {
				value += va;
				recs.push({t.first, rc});
			}
		}
		int size = recs.size();
		while (!recs.empty()) {
			recs.pop();
		}
		return {value, size};
	};

	long long left = 0;
	long long right = 1e12;
	while (left < right) {
		long long mid = (left + right) / 2;
		auto ch = check(mid);
		if (ch.second > k)
			left = mid + 1;
		else
			right = mid;
	}
	auto ch = check(left);
	return ch.first - left * ch.second;
}

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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