Submission #42681

#	Time	Username	Problem	Language	Result	Execution time	Memory
42681		despasito	Aliens (IOI16_aliens)	C++14	0 / 100	5 ms	5344 KiB

aliens

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<
	T,
	null_type,
	less<T>,
	rb_tree_tag,
	tree_order_statistics_node_update>;

// gives the number of keys with value strictly less than x
#define lesscount(x) order_of_key(x)
// gives the iterator to kth element (starting from 0)
#define kthiterator(x) find_by_order(x)

#define clock_starts() clock_t begin = clock()
#define clock_ends() clock_t end = clock()
#define print_running_time() double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC; \
printf("Elapsed Time : %.10f second(s)\n", elapsed_secs)
#define readfile(s) freopen(s, "r", stdin)
#define writefile(s) freopen(s, "w", stdout)
#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define cin_cout_is_cool ios_base::sync_with_stdio(false); cin.tie(NULL)
#define PrintBinary(n) cout << #n << " = " << bitset<64>(n) << endl
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'
#define cin(n) scanf("%d", &n)
#define popcount(x) __builtin_popcount((x))
#define popcountll(x) __builtin_popcountll((x))

inline int myrand(int l, int r) {
	int ret = rand(); ret <<= 15; ret ^= rand();
	if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
	return ret;
}
template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
    return os<<"(" <<p.first<<", "<<p.second<<")"; }

typedef pair<int, int> ii;
template<typename T> using min_pq =
	priority_queue<T, vector<T>, greater<T> >;

template<typename T>T max(T a_,T b_,T c_) { return max(a_,max(b_,c_)); }
template<typename T>T min(T a_,T b_,T c_) { return min(a_,min(b_,c_)); }
template<typename T>T min(T a_,T b_,T c_, T d_) { return min(min(a_, b_),min(c_,d_)); }
template<typename T>T max(T a_,T b_,T c_, T d_) { return max(max(a_, b_),max(c_,d_)); }

//int dx[] = {-1, +0, +1, +0};
//int dy[] = {+0, +1, +0, -1};

template<typename T> inline T ceil(T num, T d)
{ return (T)(num/d) + (num%d>(T)0 ? (T)1 : (T)0); }
#define block_no(idx) 		(idx/BLOCK_SIZE)
#define block_starting(idx) (block_no(idx)*BLOCK_SIZE)
#define block_ending(idx) 	(min(n, block_no(idx)*BLOCK_SIZE+BLOCK_SIZE-1))
#define block_rank(idx) 	(idx%BLOCK_SIZE)

typedef long long ll;
const ll is_query = LLONG_MIN+1LL;
struct Line {
    ll m, b;
    mutable function<const Line*()> succ;
    bool operator<(const Line& rhs) const {
        if (rhs.b != is_query) return m < rhs.m;
        const Line* s = succ();
        if (!s) return 0;
        ll x = rhs.m;
        return b - s->b < (s->m - m) * x;
    }
};
struct HullDynamic : public multiset<Line> {
    bool bad(iterator y) {
        auto z = next(y);
        if (y == begin()) {
            if (z == end()) return 0;
            return y->m == z->m && y->b <= z->b;
        }
        auto x = prev(y);
        if (z == end()) return y->m == x->m && y->b <= x->b;
        return 1.0*(x->b - y->b)*(z->m - y->m) >= 1.0*(y->b - z->b)*(y->m - x->m);
    }
    void addline(ll m, ll b) {
        auto y = insert({ -m, -b });
        y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
        if (bad(y)) { erase(y); return; }
        while (next(y) != end() && bad(next(y))) erase(next(y));
        while (y != begin() && bad(prev(y))) erase(prev(y));
    }
    ll query(ll x) {
        auto l = *lower_bound((Line) { x, is_query });
        return -(l.m * x + l.b);
    }
};

vector<int> L, R;
vector<ii> All;
int n, m, k;
map<ii, int> same;
vector<vector<ll> > dp;
HullDynamic cht[50010];

inline ll sq(ll x) {
	return x * x;
}

long long take_photos(int32_t N, int32_t M, int32_t K, vector<int32_t> RR, vector<int32_t> CC) {
	n = N, m = M, k = K;
	for(int i=0; i<n; i++) {
		int x, y;
		tie(x, y) = ii(RR[i], CC[i]);
		if(x > y) swap(x, y);
		if(same.find(ii(x,y)) == same.end())
			same[ii(x,y)], All.push_back(ii(x,y));
	}
	sort(all(All));
	{
		vector<int> tick;
		tick.assign(All.size(), 1);
		typedef tuple<int, int, int> trio;
		vector<tuple<int, int, int> > temp;
		for(int i=0; i<All.size(); i++) {
			ii b = All[i];
			temp.push_back(trio(b.first, +1, -i));
			temp.push_back(trio(b.second, -1, -i));
		}
		sort(all(temp));
		int c = 0;
		for(trio b : temp) {
			int x, op, id;
			tie(x, op, id) = b;
			if(op == -1) {
				c--;
				if(c) tick[-id] = 0;
			}
			else c++;
		}
		for(int i=0; i<All.size(); i++) {
			if(tick[i]) {
				L.push_back(All[i].first);
				R.push_back(All[i].second);
			}
		}
	}
	n = L.size();
	k = min(n, k);
	dp.assign(k+3, {});
	dp[1].assign(n+3, 0);
	for(int i=0; i<n; i++) {
		dp[1][i] = (R[i]-L[0]+1)*(R[i]-L[0]+1);
	}
	for(int i=2; i<=k; i++) {
		dp[i].assign(n+3, 0);
		dp[i][0] = (R[0]-L[0]+1)*(R[0]-L[0]+1);
		for(int j=1; j<n; j++) {
			cht[i].addline(-2*L[j], dp[i-1][j-1]+sq(L[j])+sq(max(0, R[j-1]-L[j]+1)));
			dp[i][j] = sq(R[j]+1) + cht[i].query(R[j]+1);
		}
		dp[i-1].clear();
	}
	return dp[k][n-1];
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int32_t, int32_t, int32_t, std::vector<int>, std::vector<int>)':
aliens.cpp:131:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<All.size(); i++) {
                 ^
aliens.cpp:147:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<All.size(); i++) {
                 ^

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