Submission #533683

#	Time	Username	Problem	Language	Result	Execution time	Memory
533683		rumen_m	Aliens (IOI16_aliens)	C++17	4 / 100	1 ms	216 KiB

aliens

#include <bits/stdc++.h>
using namespace std;

#define jjs(i, s, x) for (int i = (s); i < int(x); ++i)
#define jjl(i, x) jjs(i, 0, x)
#define ji(x) jjl(i, x)
#define jj(x) jjl(j, x)
#define jk(x) jjl(k, x)
#define jij(a, b) ji(a) jj(b)
#define jij2d(v) jij((v).size(), (v)[i].size())
#define jjdescent(i, s, e) for (int i = (s)-1; i >= int(e); --i)
#define jjrev(i, s) jjdescent(i, s, 0)
#define foreach(x, C) for (auto& x : (C))
#define INF ((int) 1e9+10)
#define LINF ((long long) 1e16)
#define pb push_back
#define mp make_pair

#define rint readInteger
template<typename T>
bool readInteger(T& x)
{
	char c, r = 0, n = 0;
	x = 0;
	while (true)
	{
		c = getchar();
		if (c < 0 && !r)
			return 0;
		else if (c == '-' && !r)
			n = 1;
		else if (c >= '0' && c <= '9')
			x = x * 10 + c - '0', r = 1;
		else if (r)
			break;
	}
	if (n)
		x = -x;
	return 1;
}

template<typename T>
vector<T> readIntegral(int n)
{
	vector<T> ret(n);
	for (int i = 0; i < n; i++)
		readInteger(ret[i]);
	return ret;
}

auto readInts = readIntegral<int>;
auto readLongs = readIntegral<long long>;

template<typename T>
vector<vector<T>> make2d(size_t r, size_t c)
{
	return vector<vector<T>>(r, vector<T>(c));
}

template<typename T>
vector<vector<T>> make2d(size_t r, size_t c, const T& def)
{
	return vector<vector<T>>(r, vector<T>(c, def));
}

template <typename T, T MOD>
struct ModInt
{
	T value;
	ModInt() : value(0)
	{}
	ModInt(T x)
	{
		x %= MOD;
		if (x < 0)
			x += MOD;
		value = x;
	}

public:
	ModInt& operator += (ModInt x)
	{
		value += x.value;
		if (value >= MOD)
			value -= MOD;
		return *this;
	}
	ModInt& operator -= (ModInt x)
	{
		value -= x.value;
		if (value < 0)
			value += MOD;
		return *this;
	}
	ModInt& operator *= (ModInt x)
	{
		value *= x.value;
		value %= MOD;
		return *this;
	}
	ModInt& operator /= (ModInt x)
	{
		x.invert();
		return *this *= x;
	}

	ModInt operator + (ModInt x) const
	{
		ModInt o = *this;
		o += x;
		return o;
	}
	ModInt operator - (ModInt x) const
	{
		ModInt o = *this;
		o -= x;
		return o;
	}
	ModInt operator * (ModInt x) const
	{
		ModInt o = *this;
		o *= x;
		return o;
	}
	ModInt operator / (ModInt x) const
	{
		ModInt o = *this;
		o /= x;
		return o;
	}
	bool operator == (ModInt x) const
	{
		return value == x.value;
	}
	bool operator != (ModInt x) const
	{
		return !(*this == x);
	}

	ModInt operator - () const
	{
		return ModInt(0) - *this;
	}

	ModInt operator ^ (long long x) const
	{
		ModInt ret = 1 % MOD;
		ModInt mul = *this;
		while (x)
		{
			if (x & 1)
				ret *= mul;
			mul *= mul;
			x >>= 1;
		}
		return ret;
	}
	ModInt& operator ^= (long long x)
	{
		return *this = *this ^ x;
	}

private:
	void invert()
	{
		*this ^= MOD-2;
	}
public:
	friend ostream& operator << (ostream& out, const ModInt& x)
	{
		return out << x;
	}
};

template<typename T>
using v2d = vector<vector<T>>;

typedef ModInt<long long, 1000000007> mint;
typedef long long ll;
typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef vector<int> VI;
typedef v2d<int> VVI;
typedef vector<ll> VLL;
typedef v2d<ll> VVLL;
typedef vector<char> VCH;
typedef v2d<char> VVCH;

PII expand(PII a, PII b)
{
	return {min(a.first, b.first), max(a.second, b.second)};
}

PII contract(PII a, PII b)
{
	return {max(a.first, b.first), min(a.second, b.second)};
}

ll area(PII x) {
	ll z = x.second - x.first + 1;
	if (z <= 0)
		return 0;
	else
		return z * z;
}

ll gain(PII a, PII b)
{
	return area(expand(a, b)) - area(a) - area(b) + area(contract(a, b));
}

ll intersect(PII a, PII b)
{
	return area(contract(a, b));
}

using qtyp = tuple<long long, PII, PII>;

qtyp makeq(PII a, PII b) {
	return qtyp {
		gain(a, b),
		a,
		b
	};
}

ll solve(int sz, int photos, VPII pts)
{
	priority_queue<qtyp, vector<qtyp>, greater<qtyp>> Q;
	set<PII> S;
	ll tot = 0;
	ji(pts.size()) {
		S.insert(pts[i]);
		tot += area(pts[i]);
		if (i+1 < pts.size()) {
			tot -= intersect(pts[i], pts[i+1]);
			Q.push(makeq(pts[i], pts[i+1]));
		}
	}
	while (S.size() > photos) {
		auto x = Q.top();
		Q.pop();
		auto it = S.find(get<1>(x));
		if (it == S.end())
			continue;
		auto a = it;
		auto b = it;
		++b;
		if (b == S.end())
			continue;
		if (*a != get<1>(x) || *b != get<2>(x))
			continue;
		tot += gain(*a, *b);
		it = S.insert(expand(*a, *b)).first;
		S.erase(a);
		S.erase(b);
		if (it != S.begin()) {
			auto prv = it;
			--prv;
			Q.push(makeq(*prv, *it));
		}
		auto nxt = it;
		++nxt;
		if (nxt != S.end()) {
			Q.push(makeq(*it, *nxt));
		}
	}
	return tot;
}

long long take_photos(int n, int m, int k, vector<int> row, vector<int> col) {
	VPII ranges;
	ji(row.size()) {
		int a = min(row[i], col[i]);
		int b = max(row[i], col[i]);
		ranges.pb({a, b});
	}
	foreach(x, ranges) x.second *= -1;
	sort(ranges.begin(), ranges.end());
	foreach(x, ranges) x.second *= -1;
	VPII nranges;
	foreach(r, ranges) {
		if (nranges.empty() || r.second > nranges.back().second)
			nranges.pb(r);
	}
	return solve(m, k, nranges);
}

// BEGIN CUT
/*
int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    std::vector<int> r(n), c(n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &r[i], &c[i]);
    }
    long long ans = take_photos(n, m, k, r, c);
    
    // BEGIN SECRET
    puts("098d134608c94f7413faac591054ee35");
    // END SECRET
    
    printf("%lld\n", ans);
    return 0;
}
*/
// END CUT

Compilation message (stderr)

aliens.cpp: In function 'll solve(int, int, VPII)':
aliens.cpp:235:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  235 |   if (i+1 < pts.size()) {
      |       ~~~~^~~~~~~~~~~~
aliens.cpp:240:18: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  240 |  while (S.size() > photos) {
      |         ~~~~~~~~~^~~~~~~~

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