Submission #361160

#	Time	Username	Problem	Language	Result	Execution time	Memory
361160		junodeveloper	Aliens (IOI16_aliens)	C++17	100 / 100	141 ms	11096 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define sz(x) ((int)x.size())
using namespace std;
#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif
template<class TH> void _dbg(const char *sdbg, TH h){cerr<<sdbg<<"="<<h<<"\n";}
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA...a){
  while(*sdbg!=',')cerr<<*sdbg++;cerr<<"="<<h<<","; _dbg(sdbg+1, a...);
}
typedef long long ll;
struct point {
	ll r,c;
	bool operator<(const point& b)const {
		return r==b.r?c>b.c:r<b.r;
	}
};
struct CHT {
	struct line {
		ll a,b,c;
	};
	vector<line> ln;
	int cur;
	void clear(){cur=0;ln.clear();}
	bool bad(line& a,line& b,line& c) {
		return (a.b-b.b)*(c.a-b.a)>(b.b-c.b)*(b.a-a.a);
	}
	bool bad2(line& a,line& b,ll x) {
		return (b.b-a.b)<x*(a.a-b.a);
	}
	void insert(ll a,ll b,ll c) {
		line t={a,b,c};
		while(sz(ln)>=2&&bad(ln[sz(ln)-2],ln.back(),t))ln.pop_back();
		ln.push_back(t);
	}
	pair<ll,ll> query(ll x) {
		cur=min(cur,sz(ln)-1);
		while(cur+1<sz(ln)&&bad2(ln[cur],ln[cur+1],x))cur++;
		return {x*ln[cur].a+ln[cur].b,ln[cur].c};
	}
}cht;
vector<point> v,tmp;
int n,m,k;
pair<ll,ll> f(ll x) {
	int i;
	pair<ll,ll> cur,pre;
	cht.clear();
	for(i=0;i<n;i++) {
		ll a=-2*(v[i].r-1);
		ll b=(v[i].r-1)*(v[i].r-1)+pre.fi;
		ll c=pre.se;
		if(i&&v[i-1].c>=v[i].r) {
			b-=(v[i-1].c-v[i].r+1)*(v[i-1].c-v[i].r+1);
		}
		//dp[i]=min((c[i]-r[j]+1)*(c[i]-r[j]+1)+dp[j-1])+x;
		cht.insert(a,b,c);
		pair<ll,ll> r=cht.query(v[i].c);
		cur={r.fi+v[i].c*v[i].c+x,r.se+1};
		pre=cur;
	}
	debug(cur.se);
	return cur;
}
long long take_photos(int n_, int m_, int k_, std::vector<int> r_, std::vector<int> c_) {
	v.clear();tmp.clear();
	n=n_,m=m_,k=k_;
	int i,j;
	for(i=0;i<n;i++) {
		if(r_[i]>c_[i])swap(r_[i],c_[i]);
		tmp.push_back({r_[i],c_[i]});
	}
	sort(tmp.begin(),tmp.end());
	for(i=0,j=-1;i<n;i++) {
		if(tmp[i].c>j) {
			j=tmp[i].c;
			v.push_back(tmp[i]);
		}
	}
	n=sz(v);
	ll lo=0,hi=1e13;
	while(lo<hi) {
		ll mid=(lo+hi)/2;
		if(f(mid).se>k)lo=mid+1;
		else hi=mid;
	}
	pair<ll,ll> ans=f(lo);
	return ans.fi-lo*k;
}

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