Submission #1104122

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104122		alexander707070	Aliens (IOI16_aliens)	C++14	100 / 100	117 ms	9660 KiB

aliens

#include<bits/stdc++.h>

#define MAXN 100007
using namespace std;

const long long inf=1e12,inff=1e18;

struct interval{
	long long l,r;

	inline friend bool operator < (interval fr,interval sc){
		if(fr.l==sc.l)return fr.r>sc.r;
		return fr.l<sc.l;
	}
}s[MAXN],w[MAXN];

struct line{
	long long a,b,from;
	int cnt;

	long long val(long long x){
		return a*x+b;
	}
};

bool smaller(line fr,line sc,long long x){
	if(fr.val(x)<sc.val(x))return true;
	if(fr.val(x)==sc.val(x) and fr.cnt<sc.cnt)return true;
	return false;
}

long long intersec(line fr,line sc){
	long long x=(fr.b-sc.b)/(sc.a-fr.a);

	if(smaller(fr,sc,x+1))x++;
	if(!smaller(fr,sc,x))x--;

	return x;
}

struct CHT{

	deque<line> d;

	void init(){
		d.clear();
	}

	void addline(line s){
		while(!d.empty() and smaller(s,d.back(),d.back().from))d.pop_back();

		if(d.empty()){
			d.push_back({s.a,s.b,-inf,s.cnt});
		}else{
			d.push_back({s.a,s.b,intersec(s,d.back()),s.cnt});
		}
	}

	pair<long long,int> query(long long x){
		while(d.size()>1 and x>=d[1].from){
			d.pop_front();
		}

		return {d.front().val(x),d.front().cnt};
	}
}hull;

int n,m,k,sz;
long long bonus[MAXN];

long long dp[MAXN];
int cnt[MAXN];

long long coef(int id){
	return -bonus[id] + dp[id-1] + w[id].l*(w[id].l-2); 
}

void solve(long long delta){
	hull.init();

	for(int i=1;i<=sz;i++){
		dp[i]=inff;
		
		hull.addline({-2*w[i].l,coef(i),0,cnt[i-1]});
		pair<long long,int> curr=hull.query(w[i].r);

		dp[i]=curr.first+w[i].r*(w[i].r+2)+delta+1; 
		cnt[i]=curr.second+1;
	}
}

long long bin(){
	long long l=-1,r=inf,tt;

	while(l+1<r){
		tt=(l+r)/2;

		solve(tt);

		if(cnt[sz]>k){
			l=tt;
		}else{
			r=tt;
		}
	}

	solve(r);
	if(cnt[sz]==k)return dp[sz]-cnt[sz]*r;
	
	long long val2=dp[sz]-cnt[sz]*r;
	long long k2=cnt[sz];

	solve(r-1);
	long long val1=dp[sz]-cnt[sz]*(r-1);
	long long k1=cnt[sz];

	return val1 + ((val2-val1)/(k2-k1))*(k-k1);
}

long long take_photos(int N, int M, int K, vector<int> r, vector<int> c){
	n=N; m=M; k=K;

	for(int i=1;i<=n;i++){
		s[i]={min(r[i-1],c[i-1])+1,max(r[i-1],c[i-1])+1};
	}

	sort(s+1,s+n+1);

	for(int i=1;i<=n;i++){
		if(sz>0 and s[i].r<=w[sz].r)continue;
		sz++; w[sz]=s[i];
	}

	for(int i=1;i<=sz;i++){
		if(w[i-1].r>=w[i].l)bonus[i]=(w[i-1].r-w[i].l+1)*(w[i-1].r-w[i].l+1);
	}

	k=min(k,sz);

	return bin();
}

/*int main(){

	hull.init();
	cout<<take_photos(5, 7, 2, {0, 4, 4, 4, 4}, {3, 4, 6, 5, 6})<<"\n";

	return 0;
}*/

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