Submission #1272671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272671		RAG27	Aliens (IOI16_aliens)	C++20	Compilation error	0 ms	0 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, int r[], 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 * k;
}

//int main() {
//	ios_base::sync_with_stdio(false);
//	cin.tie(NULL);
//	int n, m, k;
//	cin >> n >> m >> k;
//	int r[n], c[n];
//	for (int i = 0; i < n; i++)
//		cin >> r[i];
//	for (int i = 0; i < n; i++)
//		cin >> c[i];
//
//	cout << take_photos(n, m, k, r, c) << "\n";
//}

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
      |         ^~~~
/usr/bin/ld: /tmp/ccRpbfRK.o: in function `main':
grader.cpp:(.text.startup+0xff): undefined reference to `take_photos(int, int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status