Submission #712472

#	Time	Username	Problem	Language	Result	Execution time	Memory
712472		SA01	Aliens (IOI16_aliens)	C++14	100 / 100	702 ms	7740 KiB

aliens

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

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt")

using ll = long long int;
using ull = unsigned long long int;
using vi = vector<ll>;
using ii = pair<ll,ll>;
using vii = vector<ii>;
using ld = long double;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T>
using ordered_set = tree < T, null_type, less<T>,
rb_tree_tag,
tree_order_statistics_node_update >;

//#ifdef SA_DEBUG
template <class T>
void print(T a) {cerr << a << endl;}
template <class T, class... V> 
void print(T a, V... b) {cerr << a << ", "; print(b...);}
#define dbg(...) cerr << "[" << __LINE__ << "] " << #__VA_ARGS__ << " :: ", print(__VA_ARGS__)
//#else
//#define dbg(...) 7
//#endif

#define eb emplace_back
#define fi first
#define se second

const ll INFL = 1e18;
const int INF = 1e9;
const double PI = acos(-1);
const ll mod = 1e9+7;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<class T, class V> 
ostream& operator << (ostream &s, pair<T, V> a){
	s << a.fi << ' ' << a.se; return s;
}

template<class T, class V> 
istream& operator >> (istream &s, pair<T, V> &a){
	s >> a.fi >> a.se; return s;
}

template<class T> 
ostream& operator << (ostream &s, vector<T> a){
	for(int i = 0; i < (int)a.size(); i++){
		if(i > 0)s << ' ' ; 
		s << a[i];
	} return s;
}

template<class T> 
istream& operator >> (istream &s, vector<T> &a){
	for(T &x : a)s >> x; 
	return s;
}

template<class T> 
void input(T a[], int l, int r, istream &s = cin){
	while(l <= r)s >> a[l++];
}

template<class T> 
void output(T a[], int l, int r, bool en = true, ostream &s = cout){
	while(l <= r){ s << a[l++];
		if(l <= r) s << ' ';
	} if(en)s << "\n";
}
const ll K = 1e4;

long long take_photos(int n, int m, int k, std::vector<int> R, std::vector<int> C) {
  vector<ii> v(n);
  for(int i = 0; i < n; i++){
		v[i] = {R[i], C[i]};
		if(v[i].fi > v[i].se)swap(v[i].fi, v[i].se);
		v[i].se = -v[i].se;
	}
	sort(v.begin(), v.end());
	
	vector<ii> V(1, ii(-1, -1));
	for(auto x : v){
		ll l, r;
		tie(l, r) = x;
		r = -r;
		if(V.back().se < r){
			V.eb(l, r);
		}
	}
	n = V.size();
	auto cost = [&](int i, int j){
		ll cst = V[j].se - V[i].fi + 1;
		cst = cst * cst;
		if(i > 0 && V[i - 1].se >= V[i].fi){
			ll temp = (V[i - 1].se - V[i].fi + 1);
			cst -= temp * temp;
		}
		return cst * K;
	};
	//dbg(V);
	auto solve = [&](ll extra){
			deque<ii> opt(1, ii(0, 1));
			vi dp(n);
			vector<int> cnt(n);
			auto getVal = [&](int i, int j){
				return dp[i] + cost(i + 1, j);
			};
			auto cmp = [&](int i, int j, int l){
				return getVal(i, l) >= getVal(j, l);
			};
			for(int i = 1; i < n; i++){
				//dp[i] = INFL;
				//for(int j = 0; j < i; j++){
					//ll x = getVal(j, i) + extra;
					//if(x < dp[i])dp[i] = x, cnt[i] = cnt[j] + 1;
				//}
				assert(opt[0].se == i);
				//dbg(i);
				//for(auto x : opt)dbg(x);
				dp[i] = getVal(opt[0].fi, i) + extra;
				cnt[i] = cnt[opt[0].fi] + 1;
				opt[0].se++;
				while(opt.size() > 1 && opt[0].se >= opt[1].se)opt.pop_front();
				while(!opt.empty() && cmp(opt.back().fi, i, opt.back().se))
						opt.pop_back();
						
				if(opt.empty()){
					opt.eb(i, i + 1);
					continue;
				}
				
				int lo = opt.back().se + 1, hi = n;
				while(lo < hi){
					int mid = (lo + hi) / 2;
					if(cmp(opt.back().fi, i, mid))hi = mid;
					else lo = mid + 1;
				}
				
				if(hi < n)opt.eb(i, lo);
				
			}
			return ii(dp[n - 1], cnt[n - 1]);
	};
	
	ll lo = 0, hi = 1e15;
	//for(int i = lo; i <= hi; i++)dbg(solve(i));
	//dbg(solve(20001));
	//dbg(solve(20000));
	//dbg(solve(19999));
	//return 0;
	while(lo < hi){
		ll mid = (lo + hi) >> 1;

		if(solve(mid).se > k)lo = mid + 1;
		else hi = mid;
	}
	ll a, b, c, d;
	tie(a, b) = solve(lo);
	//tie(c, d) = solve(lo + 1);
	//if(d < k)k = b;
	//assert(a % K == lo * k % K);
	return (a - lo * k + K - 1) / K;
	
}
/*

5 7 2
0 3
4 4
4 6
4 5
4 6

2 6 2
1 4
4 1

*/

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:166:11: warning: unused variable 'c' [-Wunused-variable]
  166 |  ll a, b, c, d;
      |           ^
aliens.cpp:166:14: warning: unused variable 'd' [-Wunused-variable]
  166 |  ll a, b, c, d;
      |              ^

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