Submission #619778

#	Time	Username	Problem	Language	Result	Execution time	Memory
619778		sofapuden	Aliens (IOI16_aliens)	C++14	16 / 100	5 ms	368 KiB

aliens

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

using namespace std;

typedef long long ll;

const ll inf = 2e14;
const int mxN = 1e5+5;

struct line{
	ll a, b;
	int cn;
	line(ll _a, ll _b, int _cn) : a(_a), b(_b), cn(_cn) {}
	line(ll _a, ll _b) : line(_a, _b, 0) {}
	ll eval(ll x){return (x-a+1)*(x-a+1)+b;}
};

vector<int> vals;

struct LCT{
	vector<line> st;
	LCT(int n) : st(4*n,line(0,inf)) {}
	void ins(line f, int l, int r, int p){
		if(l > r)return;
		int m = (l+r)>>1;
		bool lf = st[p].eval(vals[l]) > f.eval(vals[l]);
		bool mf = st[p].eval(vals[m]) > f.eval(vals[m]);
		if(mf)swap(st[p],f);
		if(lf == mf)ins(f,m+1,r,p<<1|1);
		else ins(f,l,m-1,p<<1);
	}
	line que(int x, int l, int r, int p){
		int m = (l+r)>>1;
		if(vals[m] == x)return st[p];
		if(vals[m] > x){
			line cu = que(x,l,m-1,p<<1);
			if(st[p].eval(x) < cu.eval(x))return st[p];
			else return cu;
		}
		else{
			line cu = que(x,m+1,r,p<<1|1);
			if(st[p].eval(x) < cu.eval(x))return st[p];
			else return cu;
		}
	}
};

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<int,int>> 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;
	}
    	for(int i = 0; i < n; ++i)vals.push_back(v[i].first);
     
     
    	// dp[n][n][k] current index : start : amount
    	// remove k with alien trick
    	// remove second n with CHT (LiChaoTree)
    	// O(n log^2(n))
    	
    	ll l = 0, r = inf, ans = 0;
    	while(l <= r){
    		ll mi = (l+r)>>1;
    		LCT lct(n);
    		lct.ins(line(v[0].second,mi,1),0,n-1,1);
    		for(int i = 1; i < n; ++i){
    			line cu = lct.que(v[i-1].first,0,n-1,1);
    			ll a = v[i].second, b = mi + cu.eval(v[i-1].first), cn = cu.cn+1;
    			if(v[i-1].first >= v[i].second){
    				if(v[i].second <= cu.a)b = mi + cu.b;
    				else{
    					b-=(v[i-1].first-v[i].second+1)*(v[i-1].first-v[i].second+1);
    				}
    			}
    			lct.ins(line(a,b,cn),0,n-1,1);
    		}
    		line cu = lct.que(v[n-1].first,0,n-1,1);
    		if(cu.cn > k){
    			l = mi+1;
    		}
    		else{
    			r = mi-1;
    			ans = cu.eval(v[n-1].first)-mi*k;
    		}
    	}
        return ans;
}

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