Submission #619961

#	Time	Username	Problem	Language	Result	Execution time	Memory
619961		sofapuden	Aliens (IOI16_aliens)	C++14	41 / 100	2029 ms	96864 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll inf = (1ll<<60);

struct Line {
	ll a, b;
	ll cn;
	ll eval(ll x) { if(b == -1)return inf; return (x-a+1)*(x-a+1) + b; }
	Line() : a(0), b(-1), cn(0) {}
	Line(ll _a, ll _b, ll _cn) : a(_a), b(_b), cn(_cn) {}
};

struct LCT {
	int n;
	vector<Line> st;
	LCT(int sz) : n(sz), st(4*n) {}

	void ins(Line f, int l = 0, int r = -1, int p = 1){
		if(r == -1)r = n-1;
		if(l > r)return;
		int m = (l+r)>>1;
		bool lb = f.eval(l) < st[p].eval(l);
		bool mb = f.eval(m) < st[p].eval(m);
		if(mb)swap(st[p],f);
		if(lb == mb)ins(f,m+1,r,p<<1|1);
		else ins(f,l,m-1,p<<1);
	}

	pair<ll,ll> que(ll x, int l = 0, int r = -1, int p = 1){
		if(r == -1)r = n-1;
		int m = (l+r) >> 1;
		if(m == x)return {st[p].eval(x),st[p].cn};
		if(m < x)return min(make_pair(st[p].eval(x),st[p].cn),que(x,m+1,r,p<<1|1));
		return min(make_pair(st[p].eval(x),st[p].cn),que(x,l,m-1,p<<1));
	}
};

ll take_photos(int n, int M, int k, vector<int> R, vector<int> C) {
	for(int i = 0; i < n; ++i)if(R[i] > C[i])swap(R[i],C[i]);
	vector<pair<ll,ll>> v, _v;
	for(int i = 0; i < n; ++i)_v.emplace_back(R[i],C[i]);
	sort(_v.begin(),_v.end());
	v.push_back(_v[0]);
	for(int i = 1; i < n; ++i){while(v.size()&& _v[i].first == v.back().first)v.pop_back();if(v.empty() || _v[i].second > v.back().second)v.push_back(_v[i]);}
	n = v.size();
	if(k >= n){
		ll ans = (v[0].second-v[0].first+1)*(v[0].second-v[0].first+1);
		for(int i = 1; i < n; ++i){
			ans+=(v[i].second-v[i].first+1)*(v[i].second-v[i].first+1);
			if(v[i].first <= v[i-1].second)ans-=(v[i-1].second-v[i].first+1)*(v[i-1].second-v[i].first+1);
		}
		return ans;
	}

	ll l = 0, r = (1ll<<40), ans = 0;
	while(l <= r){
		ll m = (l+r)>>1;
		LCT lct(M+5);
		lct.ins(Line(v[0].first,m,1));
		for(int i = 1; i < n; ++i){
			pair<ll,ll> cu = lct.que(v[i-1].second);
			ll a = v[i].first, b = m+cu.first, cn = cu.second+1;
			if(v[i].first <= v[i-1].second){
				b-=(v[i-1].second-v[i].first+1)*(v[i-1].second-v[i].first+1);
			}
			lct.ins(Line(a,b,cn));
		}
		pair<ll,ll> cu = lct.que(v[n-1].second);
		if(cu.second > k){
			l = m+1;
		}
		else{
			r = m-1;
			ans = cu.first-m*k;
		}
	}
	return ans;
}

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