Submission #358537

#	Time	Username	Problem	Language	Result	Execution time	Memory
358537		junodeveloper	Aliens (IOI16_aliens)	C++17	0 / 100	1 ms	364 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;
	}
};
// max cht
// cht.insert({a,b})
// cht.query(x)
struct CHT {
	struct line {
		ll first;
		ll second;
		ll count;
		bool operator<(const line& b)const{
			if(first==b.first) {
				if(second==b.second)return count<b.count;
				return second<b.second;
			}
			return first<b.first;
		}
	};
	using frac=pair<ll,line>;
	const ll INF=1e15;
	set<line> ls;
	set<frac> fs;
	inline frac getf(line a,line b) {
		if(b.fi>a.fi) return {(a.se-b.se)/(b.fi-a.fi)-((a.se-b.se)%(b.fi-a.fi)<0),b};
		return {(b.se-a.se)/(a.fi-b.fi)-((b.se-a.se)%(a.fi-b.fi)<0),b};
	}
	void clear() {
		ls.clear();fs.clear();
	}
	void addln(line ln) {
		auto it=ls.lower_bound(ln);
		if(it!=ls.end()) {
			if(it==ls.begin()) fs.erase({-INF,*it});
			else fs.erase(getf(*prev(it,1),*it));
			fs.insert(getf(ln,*it));
		}
		if(it!=ls.begin())
			fs.insert(getf(*prev(it,1),ln));
		else fs.insert({-INF,ln});
		ls.insert(ln);
	}
	set<line>::iterator removeln(set<line>::iterator it) {
		if(it!=ls.begin())
			fs.erase(getf(*prev(it,1),*it));
		else fs.erase({-INF,*it});
		if(next(it,1)!=ls.end()) {
			fs.erase(getf(*it,*next(it,1)));
			if(it!=ls.begin())
				fs.insert(getf(*prev(it,1),*next(it,1)));
		}
		return ls.erase(it);
	}
	inline bool bad(line a,line b,line c) {
		return getf(b,c)<=getf(a,b);
	}
	void insert(line newline) {
		auto it=ls.lower_bound({newline.fi,-INF,0});
		if(it!=ls.end()&&it->fi==newline.fi) {
			if(it->se<newline.se) it=removeln(it);
			else return;
		}
		if(it!=ls.end()&&it!=ls.begin()&&bad(*prev(it,1),newline,*it))
			return;
		if(it!=ls.begin()) {
			auto jt=prev(it,1);
			while(jt!=ls.begin()&&bad(*prev(jt,1),*jt,newline)) {
				jt=removeln(jt);
				jt--;
			}
		}
		while(it!=ls.end()&&next(it,1)!=ls.end()&&bad(newline,*it,*next(it,1)))
			it=removeln(it);
		addln(newline);
	}
	pair<ll,ll> query(ll x) {
		auto it=fs.lower_bound({x,{-INF,-INF,0}});
		if(it==fs.begin()) return {-INF,0};
		it--;
		return {(it->se.fi)*x+(it->se.se),it->se.count};
	}
}cht;
vector<point> v,tmp;
int n,m,k;
void add(ll a,ll b,ll c) {
	cht.insert({-a,-b,c});
}
pair<ll,ll> query(ll x) {
	pair<ll,ll> ret=cht.query(x);
	return {-ret.fi,ret.se};
}
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+x;
		ll c=pre.se;
		if(i) {
			b-=max((v[i-1].c-v[i].r+1)*(v[i-1].c-v[i].r+1),0ll);
		}
		add(a,b,c);
		pair<ll,ll> r=query(v[i].c);
		cur={r.fi+v[i].c*v[i].c,r.se+1};
		pre=cur;
	}
	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-ans.se*lo;
}

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