Submission #290274

#	Time	Username	Problem	Language	Result	Execution time	Memory
290274		shayan_p	Aliens (IOI16_aliens)	C++17	100 / 100	446 ms	6380 KiB

aliens

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

#define F first
#define S second
#define PB push_back
#define sz(s) (int(s.size()))
#define bit(n, k) (((n)>>(k)) & 1)

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;

const int maxn = 1e5 + 10, mod = 1e9 + 7;
const ll inf = 1e13 + 10, INF = 1e18;

pll dp[maxn];
int mn[maxn];

struct CHT{
    deque<pair<pll, ll>> v;
    long double cross(pll a, pll b){
	//	a.F * x + a.S == b.F * x + b.S;
	return (long double)(b.S - a.S) / (a.F - b.F);
    }
    bool bad(pll a, pll b, pll c){
	long double A = cross(a, b), B = cross(b, c);
	return A < B;
    }
    pll eval(int id, ll x){
	return {v[id].F.F * x + v[id].F.S, v[id].S};	
    }
    void add(ll a, ll b, ll c){
	if(!v.empty() && v.back().F.F == a){
	    if(v.back().F.S < b)
		return;
	    if(v.back().F.S > b){
		v.pop_back();
	    }
	    else{
		if(v.back().S < c)
		    return;
		v.pop_back();
	    }
	}
	while(sz(v) > 1 && bad(v[sz(v)-2].F, v[sz(v)-1].F, {a, b}))
	    v.pop_back();
	while(sz(v) > 1 && cross(v[sz(v)-2].F, v[sz(v)-1].F) == cross(v[sz(v)-1].F, {a, b}) && v[sz(v)-1].S >= min(c, v[sz(v)-2].S))
	    v.pop_back();
	v.PB({{a, b}, c});
    }
    pll ask(ll x){
	while(sz(v) > 1 && eval(0, x) > eval(1, x))
	    v.pop_front();
	return eval(0, x);
    }
    void clear(){
	v.clear();
    }
};CHT cht;

pll solve(vector<pii> &seg, ll c){
    cht.clear();
    cht.add(seg[0].F, 1ll * seg[0].F * seg[0].F, 0);
    for(int i = 1; i <= sz(seg); i++){
	int mn = i == sz(seg) ? (seg[i-1].S + 1) : seg[i].F;
	mn = min(mn, seg[i-1].S + 1);
	dp[i] = cht.ask(-2 * (seg[i-1].S + 1));
	dp[i].F+= -1ll * mn * mn + 2ll * (seg[i-1].S + 1) * mn + c;
	dp[i].S++;
	if(i < sz(seg))
	    cht.add(seg[i].F, dp[i].F + 1ll * seg[i].F * seg[i].F, dp[i].S);
    }
    return dp[sz(seg)];
}
ll take_photos(int m, int n, int k, vector<int> X, vector<int> Y){
    vector<pii> _seg, seg;
    for(int i = 0; i < m; i++){
	if(X[i] > Y[i])
	    swap(X[i], Y[i]);
	_seg.PB({X[i], Y[i]});
    }
    sort(_seg.begin(), _seg.end());
    for(pii p : _seg){
	if(seg.empty() || seg.back().S < p.S)
	    seg.PB(p);
    }
    
    ll l = -1, r = inf;
    while(r-l > 1){
	ll mid = (l+r) >> 1;
	pll p = solve(seg, mid);
	if(p.S > k)
	    l = mid;
	else
	    r = mid;
    }
    pll p = solve(seg, r);
    return 1ll * p.F - 1ll * k * r;
}

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